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 set in the table.

[ghasempouri1984]

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

[Veronicaonofri]

[LudovicaErre]

[ManueleVeggi]

I attach my solution proposal for this exercise:

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

On "Turing machine Visualization" this can be rendered as:

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:

[Bianca-LM]

Current state____Tape symbol_____Write symbol____Move head______Next state
A_________________read 0 or 1____________0_______________left_______________B_____
B_________________read 0 or 1____________1______________right______________C______
C_________________read 0 or 1____________0______________right______________B______
B_________________read 0 or 1____________1______________right______________D______

[CarmenSantaniello]

[olgagolgan]

[tommasobattisti]

Table of instructions:

CURRENT STATE	TAPE SYMBOL	WRITE SYMBOL	MOVE HEAD	NEW STATE
A	0	1	Left	B
A	1	0	Right	C
B	0 or 1	1	Right	A
C	0 or 1	1	Left	D

On "Turing machine visualization":

[martasoricetti]

[giorgimariachiara]

Current state | Tape symbol | Write symbol | Move head | Next state

A | 0 | 1 | right | B
A | 1 | 0 | left | C
B | 0 | 1 | left | A
C | 0 | 1 | left | D

[angstigone]

[sarabecchi]

[OrsolaMBorrini]

I found it much easier to understand using the Turing machine visualization.
I don't think it is the case, but I was wondering if the order of the instructions within the table is of any importance or not...

[victorchaix]