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.

[diegochillo]

Turing machine that writes 101 around the initial cell:

input: ''
blank: '0'
start state: A
table:

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

    B:
    [0]: {write: 1, R}
    [1]: {write: 0, R: C}

    C:
    [0]: {write: 1, R: D}

    D:

[fcagnola]

This is my proposed solution, I think it'll work

Current state	Symbol	Write	Move	Next state
A	0/1	1	Right	B
B	0/1	0	Right	C
C	0/1	1	Right	D

Starting state: A Ending state: D

[edoardodalborgo]

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

[DeniseBas]

[SarahTew]

I don't understand how to do this unless it's possible to move the header two spaces at once. (or move the header without it being part of a state??) I'm going to through my understanding of all the answers posted so far. Please please please if you think you understand this and your answer is right, please reply to me and explain. I think I am misunderstanding some sort of key information about Turing machines and/or the stipulations within the question.

@diegochillo's and @fcagnola write a 1 in the initial cell, which is incorrect since the instructions said that one had to be 0 and only the immediately adjacent cells should contain 1. @giorgiasampo's does make 1 0 1 with the 0 being in original cell position of the header but contains instructions for state D which is forbidden. @edoardodalborgo's doesn't work when you write 0 as in state A. It sends you to state C where you write a one and it finishes so it just says 01. Right? What am I missing? Is it something about how the cells are set up before state A begins? Is it the definition of instructions that I've misunderstood and a table that looks like @giorgiasampo's with stuff in state D is allowed? Is the origin cell of the header different from the origin cell of state A?

I've tried reusing a state like @DeniseBas but it just traps me in an endless loop. Can you have one state with two different sets of instructions and next states (as in Denise's state A)??? I wouldn't think so but I am lost as to how to actually do this with only states A, B, and C containing instructions, moving one space at a time, and each phase being exactly the same each time it is used.

[LuisAmmi]

I agree with SarahTew, something's not right. The prohibition on specifing any instruction for the final state D makes the problem complex. Indeed, the text tells us that once reached the final state (so, after the transition from C to D),2 cells (the ones immediately on the left and on the right of the inital position of the head, which means the cells pointed by the head during the state C and A) will change value to 1. If this change must take place simultaneously, we can say (if I have understood correctly how the Touring machine works) that there is no solution, because the head of the machine points one cell at a time and write one symbol at a time. Moreover, if D has no instruction we cannot proceed writing new symbols in cells. The table tell us the machine has to stop. But we also cannot anticipate the change of symbols before, because the text specify that only once reached the D state, we should write 1 in those two cells. Maybe this argument is uncorrect, anyway I can not find other solutions.

[diegochillo]

@SarahTew who wrote:

@diegochillo's and @fcagnola write a 1 in the initial cell, which is incorrect since the instructions said that one had to be 0 and only the immediately adjacent cells should contain 1.

Dear Sarah, The instructions state that you have to get the 101 "once reached the final state". During the process, you can write what you want where you want. I restore the 0 in the initial cell at the B state.

[alicebordignon]

[ConstiDami]

Current state	Tape symbol	Write symbol	Move head	Next State
A	0	1	R	B
A	1	0	L	C
B	0	1	L	A
C	0	1	R	D
D

At first I was confused because I thought that at the beginning of the execution, the cells could contain either 0 or 1, but after rereading the book chapter, I saw that all the cells are assigned to 0 in advance! I don't know if this information can help other people... :)

[GiuliaMenna]

Initial state: A Final state: D

Only the cells immediately on the left and on the right of the initial position A have the value 1 specified.

[SarahTew]

@diegochillo I am still confused so I've copied your algorithm here for reference and below it I have written out when happens when I follow the algorithm and the problems that still aren't resolved. I still don't understand if I'm misreading the question and/or your algorithm.

input: '' blank: '0' start state: A table:

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

B:
[0]: {write: 1, R}
[1]: {write: 0, R: C}

C:
[0]: {write: 1, R: D}

D:

Let the bold number be the number in the initial position cell. Let __ represent a cell with nothing written in it (it is either blank or contains something for the machine to read that you have not written)

At the end of state A you have 1 then you move left and to State B. At the end of state B you have either 1 1 then you move right but there's no subsequent state (Why does it end here?) or 0 1 then you move right and move to State C At the end of the State C you have 0 1__ then you move to State D.

All of the scenarios above end with a 1 in the initial cell. You don't replace it with 0 in State B because you've moved to the left; you're putting a 0 in the cell to the left of your initial starting place. They also don't contain 1s in the cells adjacent to the initial cell. How is your algorithm supposed to work? How are you getting 1 0 1 ?

[diegochillo]

@SarahTew

input:'' and blank: '0' mean that all the cells are initially filled with symbol '0'.

then you move right but there's no subsequent state

When there's no state specified, it means that you remain in the same state you are.

So the sequence is:

Initial symbols: 000

A: regardless of the symbol (1 or 0), write 1 on the initial cell, move left and switch to state B (Symbols: 010)

B: cursor is left to initial cell, there's a 0, so write 1 and move right (Symbols: 110)

B: cursor is back on initial cell, there's a 1, so write 0, move right and switch to state C (Symbols: 100)

C: cursor is right to the initial cell, there's a 0, so write 1, move right and switch to final empty state D (Symbols: 101)

...as ou can check on https://turingmachine.io/

Hope this helps.

[lauratravaglini]

Current State	Tape symbol	Write symbol	Move head	Next state
A	1	0	right	B
B	0	1	right	C
C	1	0	right	D

D

[SarahTew]

@diegochillo Thank you!!! I understand now! For those following the replies: The key is that you don't have to assign a next state (duh!), that's how you can use the same state twice. See @diegochillo's latest reply for a step by step explanation. Mystery solved! Thank you!

[laurentfintoni]

input: '01' blank: ' ' start state: a table: a: '0': {L: b} b: ' ': {write: 1, R: c} c: '0': {R: b} d:

seems to work using https://turingmachine.io/

[giorgiasampo]

[gabrielefiorenza]

[Camillaneri]

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

Start state: A End state: D

[vanessabonanno]

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

The output should be: ... 0 0 0 1 0 1 0 0 0 ... This is how I tried solving this exercise, but I still have one big doubt: what is the "initial position" that have to present on its immediately near cells "1"?

[AlessandraFa]

[AlessandroBertozzi]

[LuisAmmi]

Initial state: A Final state: D

[essepuntato]

Hi all,

Besides the varous correct answers I've seen here, I have to say that the discussion in this exercise was one of the best ones I've seen in the past four years. Thanks for that!