Lecture "Computability", exercise 1
essepuntato opened this issue · 18 comments
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.
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:
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:
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______
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":
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
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...
In the initial state A, the symbol on the tape is 0 by default, so the instruction says to write 1 on the cell of the initial position and move left. Now we can fill the cell on the immediate left of the initial position with the digit 1; indeed, we will pass to the state B, which says to write 1 and move right, so we will be again on the initial position. With the current state set on A, this time the symbol on the tape is 1, so the instruction of the state A says to write a 0 and then move right, in order to fill the cell on the immediate right of the initial position and, according to the state C, we will write 1 and move right to the final state D. In the end, we will have the digit 1 just inside the cells to the immediate left and right of the initial position.
