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.

[ilsamoano]

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:

[hizclick]

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

[ilsamoano]

that's nice! I didn't think about to use the new A state!

[giuliapl]

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

[MattiaSpadoni]

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:

[lisasiurina]

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

[LuciaGiagnolini12]

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

[EleonoraPeruch]

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

[SeverinJB]

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

[friendlynihilist]

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:

[delfimpandiani]

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!

[ilsamoano]

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

[tceron]

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.

[essepuntato]

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: