CS 10, Fall 1997 -- Lab 12

CS 10, Fall 1997

Lab 12: Turing Machines

Assignment for the Next Lab

Read pages 274-287 from Module 7 before next lab period.

Lab 12 Instructions

Today, you will be testing simple Turing Machines and describing their behavior in high-level terms (that is, do these machines perform arithmetic or logical functions? If so, which ones?). The objective of this exercise is to help you appreciate that something as simple as a Turing Machine is capable of performing any computational task (that is, anything a general purpose computer can do).

Copy the "module7" folder on the "Classes" file server to your disk.
Do lab exercise 1 on page 271. Try the following inputs for TM1 and record the output produced. Describe TM1's function to the right of the table given below.
```
TM1
   Input              Output

   1. 011001!bbbbbb   1.
   2. 111!bbb         2.
   3. 00!bb           3.
   4. 0101!bbbb       4.
   5. 1101!bbbb       5.
```
Try the following inputs for TM2 and record the output produced. Create more tests of your own to fill out the table. Describe TM2's function in high-level terms to the right of its table (note that TM2 assumes unary numbers, described in ex. 1.10).
```
TM2
   Input              Output

   1. 111b            1.
   2. 1b              2.
   3.                 3.
   4.                 4.
   5.                 5.
```

Do lab exercise 2 on page 279. Try to discover each Turing machine's intended purpose by experimenting with test inputs. Record your tests in the tables below. Provide a high-level description of each Turing machine's function, if you can. Several of these machines work with unary numbers which are described in Exercise 1.10 on p. 274.

TM3
   Input              Output                 TM3 description:

   1.                 1.
   2.                 2.
   3.                 3.
   4.                 4.
   5.                 5.

TM4
   Input              Output                 TM4 description:

   1.                 1.
   2.                 2.
   3.                 3.
   4.                 4.
   5.                 5.

TM5
   Input              Output                 TM5 description:

   1.                 1.
   2.                 2.
   3.                 3.
   4.                 4.
   5.                 5.

TM6
   Input              Output                 TM6 description:

   1.                 1.
   2.                 2.
   3.                 3.
   4.                 4.
   5.                 5.

Create a Turing Machine of your own. This machine should take a string of 1's and 0's and flip each bit. So every 1 should be converted to a 0 and every 0 should be converted to a 1. The table below shows what the output should be for several inputs. Write the rules for this TM and save it under the name "MyTM".
```
   Input              Output

   1. 1111            1. 0000
   2. 101             2. 010
   3. 0011100         3. 1100011
```
Call one of us over and demonstrate your Turing Machine.