Lecture "Computability", exercise 1
Opened this issue · 14 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 specified in the table.
I've initially tried trying to stick to the process
blank: '0'
start state: A
table:
A:
0: { write: 0, L: B }
B:
0: { write: 1, R: C }
C:
0: { write: 0, R: D }
D:
0: { write: 1, L: A }
...and I miserably failed ("D" needed a state instruction to print the 1 on the right side of the initial position), so I've tried to modify the context..and it worked, but I can't really say if this was the method intended to be used..I feel like I've cheated
input: '0100'
blank: ' '
start state: A
table:
A:
0: {write: 0, L: B}
B:
' ': {write: 1, R: C}
C:
0: {write: 0, R: D}
D:
blank: '0'
start state: A
table:
A:
0: {write: 1, L: B}
1: {write: 0, R: C}
B:
0: {write: 1, R: A}
C:
0: {write: 1, R: D}
D:
this worked for me
that's nice! I didn't think about to use the new A state!
blank: '0'
start state: A
table:
A:
0: {write: 1, L: B}
1: {write: 0, R: C}
B:
0: {write: 1, R: A}
C:
0: {write: 1, R: D}
D:
end state: D
input: ''
blank: '0'
start state: A
table:
A:
0: {write: 1, R: B}
1: {write: 1, R: D}
B:
0 : {write: 1, R: C}
C:
0 : {write: 1, L: C}
1 : {write: 0, L: A}
D:
2:
(it has shorter instructions)
input: ''
blank: '0'
start state: A
table:
A:
0 : {write: 1, R: B}
B:
0 : {write: 0, R: C}
C:
0 : {write: 1, L: D}
D:
blank: '0'
start state: A
table:
A:
0: {write: 1, L: B}
1: {write: 0, R: C}
B:
0: {write: 1, R: A}
C:
0: {write: 1, R: D}
end state: D
I'll try to express what I've thought with words, but I'm definitely not sure if I've understood well the mechanism (if not, can someone please correct me?)
blank: '0'
start state: A
table:
A:
0: {write: 1, L: B} The tape is initialized with 0, so the machine reads "0", then writes "1" (and turns left to state B)
1: {write: 0, R: C} So, since the machine has previously wrote it, now in state A there's "1": the machine reads "1", then writes "0" (and turns right to state C)
B:
0: {write: 1, R: A} In state B the machine reads "0", writes "1" and move right to A
C:
0: {write: 1, R: D} In state C the machine reads "0", writes "1" and move right to D
D:
end state: D
I have tried to solve the issue by creating a proper table as we saw in class; however I'm not sure about the sequence of instructions:
| Current state | Tape symbol | Write symbol | Move tape | Next state |
|---|---|---|---|---|
| A | 0 or 1 | 0 | left | B |
| B | 0 or 1 | 1 | right | C |
| C | 0 or 1 | 1 | right | D |
| D | 0 or 1 | 0 |
After today's lecture I provide the correction to the previous table. Here I reuse the state A.
| Current state | Tape symbol | Write symbol | Move tape | Next state |
|---|---|---|---|---|
| A | 0 or 1 | 1 | left | B |
| B | 0 or 1 | 1 | right | A |
| A | 0 or 1 | 0 | right | C |
| C | 0 or 1 | 1 | right | D |
| D | 0 or 1 | 0 |
Given a tape which initially has only zeros.
Blank: ... 0000 ...
| Tape symbol | Current state (A) | Current state (B) | Current state (C) | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Write symbol | Move tape | Next state | Write symbol | Move tape | Next state | Write symbol | Move tape | Next state | |
| 0 | 1 | L | B | 1 | R | A | 1 | L | D |
| 1 | 0 | R | C | ||||||
They both work, I've just changed the directions.
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:
blank: '0'
start state: A
table:
A:
0: {write: 1, L: B}
1: {write: 0, R: C}
B:
0: {write: 1, R: A}
C:
0: {write: 1, R: D}
D:
My original approach (before giving a look to you guys') gives the right result but has the defect of running forever:
| Current State | Type Symbol | Write Symbol | Move Type | Next State |
|---|---|---|---|---|
| A | 0 or 1 | 0 | L | B |
| B | 0 or 1 | 1 | R | C |
| C | 0 or 1 | 0 | R | D |
| D | 0 or 1 | 1 | L | A |
blank: '0'
start state: A
table:
A:
0: {write: 0, L: B}
1: {write: 0, L: B}
B:
0: {write: 1, R: C}
1: {write: 1, R: C}
C:
0: {write: 0, R: D}
1: {write: 0, R: D}
D:
0: {write: 1, L: A}
1: {write: 1, L: A}
I looked at you guys' approaches and it all made sense to me when I realized I could have the initial box be 1 and then change it back to 0. Smart!
blank: ' '
start state: A
table:
A:
' ': {write: 0, R: B}
0: {L: C}
B:
' ': {write: 1, L: A}
C:
' ': {write: 1, L: D}
D:
blank: '0'
start state: A
table:
A:
Read 0: {write: 1, Left: B}
or
Read 1: {write: 0, Right: C}
B:
Read 0: {write: 1, Right: A}
C:
Read 0: {write: 1, R: D}
D:
End state.
Hi all,
I'm providing the solution to this exercise so as to be reused in the Turing Machine Visualization tool for testing it:
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: