History and Philosophy of Computing Turing Computability

Exercise 1 Provide the configuration table of a TM that alternates 1, 0 with interleaving blanks starting from any input tape (i.e. not necessarily blank).

Exercise 2 Provide the configuration table of a TM that performs multiplication by 2.

Exercise 3 Provide the configuration table of a TM that performs addition as informally defined above.

Exercise 4 Provide the configuration table of a TM that performs multiplication as informally defined above.

Exercise 5 Provide the configuration table of a Turing Machine that starts with a tape containing a block of n 1s for n an integer of your choice and it is otherwise blank. The machine, started scanning the leftmost 1 on the paper, it halts scanning the rightmost 1 on the tape. The machine does not either print nor erase anything. Which function is this machine implementing?

Exercise 6 Provide the configuration table of a Turing Machine that starts with a tape containing a block of n 1s for n an integer of your choice and it is otherwise blank. The machine, started scanning the leftmost 1 on the paper, it halts after scanning the rightmost 1 on the tape and having deleted all of them. Which function is this machine implementing?

Exercise 7 Provide the configuration table of a Turing Machine that starts with a tape containing a block of n 1s, followed by a blank, followed by a block of m 1s. The machine is started scanning the leftmost 1 of the block of n 1s, and halts scanning the rightmost 1 of a block of n + m 1s on the tape. Which function is this machine implementing?

Exercise 8 Provide the configuration table of a Turing Machine that starts with a tape containing a block of n 1s for n an integer of your choice and it is otherwise blank. The machine, started scanning the leftmost 1 on the paper, it halts scanning the rightmost 1 of a block of n × 2 inputs of 1s. Which function is this machine implementing?

Exercise 9 Provide the configuration table of a Turing Machine that starts with a tape containing a block of n 1s, followed by a blank, followed by a block of m 1s, followed by a blank, followed by a block of k 1s. The machine is started scanning the leftmost 1 of the block of n 1s, and halts scanning the rightmost 1 of a block of n - 1 1s, followed by a block of m + 1 1s, followed by a blank, followed by a block of k + 1 1s. Which functions is this machine implementing?

Exercise 10 Start trying the following program:

#! start s

#! end e

#! fill*

# keep 1 and move to the right

s 1 1 R s

# change 0 with 1andmove to the right

s 0 1 R s

# stop, when the end of the word was reached

s * * N e

First, can you say what this program does? Now load it into Tursi (File -> Open); enter an input in the Tape window and press Enter to load it on the tape. Execute the program by clicking on the green play button. Observe the result and check if it confirms your intuition about the program. Try few other inputs.

Exercise 11 Write a Tursi program that simulates a binary incrementer. Given a binary number, it returns on tape the next higher binary number. To do that, the machine state table is defined by three states:

State 0 if reading an empty cell * the machine moves the head left and goes into the next state;

if reading 0, it keeps 0 and moves right remaining in the same state;

if reading 1, it keeps 1 and moves right remaining in the same state;

State 1 If it reads *, it write 1 and moves right, going into state 2

If it reads 0, it writes 1 to increment it and moves left, going into state 2;

If it reads 1, it writes 0; because the machine has to carry a ‘1' over to the digit to the left, it will move the head to the left and stay into state 1;

State 2 If it reads, * it writes the same, the input is finished so it can move left and halt

If it read 0 it writes 0, moves right and stays in state 2

If it read 1 it writes 1, moves right and stays in state 2.

As for the previous exercise, load the program into Tursi and enter a binary input and check that its execution increases to the next binary (you can use your knowledge of binary to check that the output corresponds to the next binary and if you are using large binary you can use an online converter to decimal).

Exercise 12 Write a program that simulates a unary subtraction. The initial tape is composed by a number made of units (e.g. 3 = 111) followed by a blank * and a smaller number made by units (e.g. 2 = 11). So in this program we always assume that the greatest number is the first input and the second number is the second input. The general idea is to delete all the 1s from the second input and delete as many from the first input, so that only the difference remains on tape. Then the machine does the following:

1. First State: it reads the first input;

2. Second State: it reads the second input;

3. Third State: it removes a 1 from the second input;

4. Fourth State: just to go over the second input to reach the first input;

5. Fifth State: starts when we have emptied the second input and want just to check that nothing is left there;

6. Sixth State: delete all the 0s in the second input and substitute them with *;

7. Seventh State: delete all the 0s in the first input and substitute them with *;

8. Eighth State: remove a 1 from the first input;

As for the previous exercise, load the program into Tursi and enter an input. In this case remember that the input is only ones: if you want to subtract 3 from 5, your input needs to be 11111 * 111. Run your program and check that the output is correct.

Exercise 13 Test and explain what the following program does:

#

#! start state0

#! end stop

#! fill * #
state0 * * l state1

state0 0 0 r state0

state0 1 1 r state0

#
state1 * 1 r state2

state1 0 1 l state2

state1 1 0 l state1

#
state2 * * l stop

state2 0 0 r state2

state2 1 1 r state2