Lecture "Computability", exercise 1

[essepuntato]

Write the table of instructions of a Turing machine with four states – A (initial state), B, C, and D (final state) – such that, once reached the final state, only the cells immediately on the left and on the right of the initial position of the head of the machine will have the value 1 specified. The final state must not have any instruction specified in the table.

[FrancescoFernicola]

Issue 1 Turing.xlsx

I've also implemented it in the Turing Machine Visualization tool as follows:

input: '0' blank: '0' start state: A table: A: [0,1]: { write: 1, R: C }

B: [0 ,1]: { write: 1, L: A }

C: '0': { write: 1, L: B } '1': { write: 0, L: D }

D:

[elisasilvad]

[arcangelo7]

blank: '0' start state: A table: A: 0: { write: 1, R: B } 1: { write: 0, L: C } B: 0: { write: 1, L: A } C: 0: { write: 1, R: D} D:

[NoonShin]

Current State	Tape Symbol	Write Symbol	Move Head	Next State
A	0	1	Right	B
A	1	0	Left	C
B	0 or 1	1	Left	A
C	0 or 1	1	Right	D

[ariannamorettj]

The first table was my first attempt. I'm not sure about the actual possibility to set the starting position of the head in a cell containing the only "1" symbol, by setting it as input among all the other cells containing the blank symbol "0". Anyway, the second version seems more logical and natural.

[noreanystrom]

The first solution is very simple and definitely the most efficient one. Although I am not sure the algorithm is suitable for a Turing Machine. The sequence is in a straight line and there is only one directive for every state. Gave it a second try and came up with solution 2

[arimuti]

[essepuntato]

Hi guys,

Here is my solution, that can be run in the Turing Machine Visualisation Tool, if you want to see what happens.

blank: '0'
start state: A
table:
  A:
    0: { write: 1, R: B }
    1: { write: 0, L: C }
  B:
    0: { write: 1, L: A }
  C:
    0: { write: 1, L: D }
  D:

Just a couple of things:

1. @arimuti you have specified two rows (row 1 and 3) having the same state and type symbol, but with different next states. In this case, it is impossible to a Turing Machine to understand if rule 1 or rule 3 should be applied according to what is read by the head.
2. @noreanystrom I would suggest you to try to convert your table of instructions in the format of the Turing Machine Visualisation Tool so as to see it in action since it seems to be there are some issues in the instructions proposed. In particular, remember that the two 1s of the output should be placed just before and after the cell pointed by the head at the very beginning.