History and Philosophy of Computing Universal Turing Machine

Exercise 1 Define a program ADD for the following:

- It starts reading the entries of a list of 0s and 1s one by one
- When it reads 0 does nothing on the input and moves right staying in
- When it reads 1 does nothing on the input and moves right staying in
- When it reads empty does nothing on the input and moves left and goes into Add state
- In Add state, when it reads 0 writes 1 and stays where it is and ends
- In Add state, when it reads 1 writes 0 and goes left and stays in Add state
- When it reads empty it writes 1 and stays where it is and ends.

What does this program do to a binary number? What to a list of 1s? what to an empty tape?

Exercise 2 Define a program ADD1 performing ADD separately on two binary numbers on the same tape, separated by *.

Exercise 3 Now define a program that takes a list of 1s and 2s and returns a sorted list with all 1s before all 2s. To do so, implement the following logic:

- the input of the machine is a list of 1s and 2s;

- first read the input from left to right
if there is a 1, keep it
as soon as you find a 2, change it to a placeholder for example 3, and move until the right end of the input

- when reached the right end, read the input from right to left
if there is a 2, keep it (and stay in this state)

if there is a 1, change it to 2, then go until the end of the input keeping everything as it is, except when you find a 3 change it into a 1 and then start again
if there is a 3 change it to 2, then move left until the first empty cell, and stop.

Note that the above description is very informal and not as detailed as the other ones. You have to figure out how many states are needed and how and when to change from state to state.

Exercise 4 Write a program for the following:
- the symbols valid for this machines are 1, 0,*
- the input is of the form r(1s * 1s)
- the machine subtracts the second series of 1s from the first

- the output is of the form r(1s0s*0s), where the list of 1s is the reminder of the subtraction, the 0s are the elements deleted respectively in the first and in the second input.

Exercise 5 Read the article by Copeland and Sommaruga (you will need to read at least sections 1, 3, 4). Explain the difference between the concept of stored-program in the theoretical sense of Turing and specify which term was used by Turing to express the notion of ‘program'. Moreover, highlights some of the other contributions to the development of this concept.

Exercise 6 Explain in which sense the development of the UTM justifies the Church-Turing thesis.