CS1101C Practical Exam

Session 1 (1000 - 1145 hours)

Turing Machine

The name of your C program file must be called turing.c, files with any other name will not be marked.

The deadline for this lab is Wednesday 12 April 2006, 11:45:59 hours. Strictly no submissions will be accepted after the deadline.

Background

A turing machine is a theoretical computing machine that is just as powerful as any state-of-the-art computer system. The functionality of a turing machine is extremely simple: a read/write head moves along a tape and reads information from (or writes information to) the tape according to a set of instructions represented as a state table. A state table consisting of six instructions is given as follows:

Each instruction of the state table consists of five integers as detailed below.

The first integer represents the current state of the machine. This can be in the range of 0 to 100.
The second integer represents the value read on the tape. The possible values range from 0 to 9.
The third integer represents the value to be written onto the tape, also ranging from 0 to 9.
The fourth integer represents a right move (1) or a left move (0) of the read/write head.
The fifth integer represents the next state of the machine with valid states in the range of 0 to 100. The value -1 signifies that the machine stops.

For example, the line "1 0 1 0 2" can be interpreted as

If the current state is 1 and the head reads a 0 on the tape, then write 1 onto the tape, move left (0) and update the machine state to 2.

Likewise, the line "2 0 0 1 -1" can be interpreted as

If the current state is 2 and the head reads a 0 on the tape, then write 0 onto the tape, move right (1) and stop the machine (-1).

The first two numbers always represent the two conditions, and the last three numbers always represent the instructions to be carried out if both the two conditions are true. At any one point, only one possible set of instructions can be executed. Notice that the conditions are always unique.

Turing Machine in Action

We use an example to show how the turing machine works. Assume the tape contains an input of "11" which represents the unary 2 (i.e. any unary N is represented as N consecutive 1s). The rest of the tape is initialized with 0s. Part of the tape is shown below. The underlined integer depicts the current position of the read/write head. The head must always start off at the leftmost 1 in the input. The initial state of the machine is always 0.

. . . 0 0 0 0 0 1 1 0 0 0 0 . . .

Since the initial state is 0 and the tape head reads a 1, we refer to the instruction "0 1 1 1 1", i.e. write a 1 onto the current position, move the head right, and update the state to 1. The status of the machine is now

. . . 0 0 0 0 0 1 1 0 0 0 0 . . .

The current state is now 1 and the head reads a 1. Using the instruction "1 1 1 1 1", we write a 1 onto the current position, move the head right, and update the state to 1.

. . . 0 0 0 0 0 1 1 0 0 0 0 . . .

The current state is 1 and the head reads a 0. The instruction "1 0 1 0 2" is to write a 1 onto the current position, move the head left, and update the state to 2.

. . . 0 0 0 0 0 1 1 1 0 0 0 . . .

The instruction "2 1 1 0 2" writes a 1 onto the current position, move the head left, and update the state to 2.

. . . 0 0 0 0 0 1 1 1 0 0 0 . . .

Again "2 1 1 0 2", so

. . . 0 0 0 0 0 1 1 1 0 0 0 . . .

Finally, "2 0 0 1 -1" writes a 0 onto the current position, move right and the machine stops. So the tape now contains as output

. . . 0 0 0 0 0 1 1 1 0 0 0 . . .

So what is computed? If you look from the position of the head towards the right, you'll see that the tape value of 11 (unary 2) at the very beginning becoming 111 (unary 3) finally. So the set of instructions of the state table performs an increment. If time permits, you can try out and hand compute for any other input.

Note that the order that the instructions are executed may not be the same as the order of the instructions in the text file.

Representing the Tape Using a Circular Array

Note that the read/write head will always begin and end at the same position on the tape. More importantly, the unpredictable nature of moving left or right requires an infinitely long tape. However, for our task, we replace this infinitely long tape with a circular tape of finite size. In effect, the read/write head can always move left or right.

Hint: Declare an array tape[LEN] to implement the tape. Just ensure that moving left from tape[0] will cycle to tape[LEN-1]; while moving right from tape[LEN-1] will cycle to tape[0].

Task

Your program will perform the following:

Read a text file containing the input value(s) and the state table;
Print out the state table and the initial tape;
Simulate the running of the turing machine by determining the specific condition that is true at each state, then executing the corresponding instruction; and
Print out the final tape.

Assumptions

The following can be assumed when designing your program.

A circular tape length of 60 will be more than sufficient for running any instruction set.
The number of instructions in a given state table will not exceed 100.
The state table will not be empty.
Given a state table, the turing machine will always terminate with the read/write head at the same starting position.
All data in a given text file are within the range of permissible values, so there is no need to perform any explicit range checking on them.

Text File

The text file will be called state.txt. The first line of the text file contains the input. For the above example of input unary 2, the first line of the file will be

1 2

The first integer represents how many inputs there are, while the rest of the integers represent input values which need to be converted to unary form. So the initial tape for the above is

. . . 0 0 0 0 0 1 1 0 0 0 0 . . .

As a second example, if the first line of the text file for a different state table is

2 3 6

this signifies that there are two inputs, 3 and 6. So the initial tape is

. . . 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 . . .

Note the starting position of the read/write head. Further note that a 0 separates each pair of inputs. Remember that the initial state is always 0. You may assume that the first line in the text file always contains positive integers.

The state.txt file for the increment function is given below.

The above will perform an increment on the value 10 and result in 11. The sample solution is given below.

Sample Run

Assuming the sample file state.txt contains lines as shown above, the following is a sample run:

STATE TABLE
-----------
0 0 0 1 0
0 1 1 1 1
1 0 1 0 2
1 1 1 1 1
2 0 0 1 -1
2 1 1 0 2

INITIAL TAPE
------------
111111111100000000000000000000000000000000000000000000000000

FINAL TAPE
----------
111111111110000000000000000000000000000000000000000000000000

So unary 10 becomes unary 11. We will always print out all 60 positions of the tape starting from the read/write head. As another example, if the sample state.txt file contains

then the output of the sample run is

STATE TABLE
-----------
0 0 0 1 0
0 1 1 1 1
1 0 1 1 2
1 1 1 1 1
2 0 0 0 3
2 1 1 1 2
3 0 0 0 3
3 1 0 0 4
4 0 0 1 -1
4 1 1 0 4

INITIAL TAPE
------------
111011111100000000000000000000000000000000000000000000000000

FINAL TAPE
----------
111111111000000000000000000000000000000000000000000000000000

giving the output of unary 9. Guess what the state table computes this time? It is the unary addition of 3 with 6. For any state table, you can test the functionality by changing the input values. Just be careful not to use large values since you are constrained by a tape length of only 60.

Three text files have been copied into your directory by the pesetup command: increment.txt and unaryadd.txt. You can choose to copy each of these files to state.txt using the UNIX command cp (see below) and execute your program, or change the filename within your program. However, please ensure that you change the filename back to state.txt within your program before submitting your final program. This is so that we can test your program with a mystery state table.

You are reminded to follow the sample output exactly; else marks will be deducted.

Do not use any structures in your program, else no credit will be given.

Remember to submit your program using the submit turing.c command, and check your submission using the check command.

All the best!

UNIX commands

Some useful UNIX commands (in case you forgot what you did in Lab 0):

“dir”: lists all the files in the directory.
“cp a.txt b.txt”: copies a.txt to b.txt.
“mv a.txt b.txt”: moves / renames a.txt to b.txt.
“cat a.txt”: shows the contents of a.txt.