Lecture "Computability", exercise 2

[essepuntato]

Consider an algorithm that takes as input a 0-1 sequence of exactly five symbols, and returns a 1 if the sequence contains at least three consecutive 1s, and returns a 0 otherwise. Implement the algorithm with a Turing machine, where the cell correspondent to the starting position of the head is where the final result must be stored. Also, the five cells following the starting position of the head are initialised with the 0-1 sequence of five symbols used as input of the algorithm.

[diegochillo]

Writes 1 in the initial cell if thee consecutive "1" appear in the five-symbols sequence (with the input below, a 0 is written because there are no consecutive ones)

input: '010101'
blank: ' '
start state: start
table:

  start:
    [1,0]: {write: 1, R: findfirst}

  findfirst:
    [1]: {write: 0, R: findsecond}
    [0]: {R}
    [' ']: {L: getbacknotfound}

  findsecond:
    [0]: {R: findfirst}
    [1]: {write: 0, R: findthird}
    [' ']: {L: getbacknotfound}

  findthird:
    [1]: {R: end}
    [0]: {R: findfirst}
    [' ']: {L: getbacknotfound}

  getbacknotfound:
    [0]: L
    [1]: {write: 0, L: end}

  end:

[edoardodalborgo]

In this solution when the algorithm catch three consecutive 0s (negative condition, if you have 3 consecutive 0s you can't have 3 consecutive 1s) in three different states (B, C, D) it ends and the solution in the first cell is just printed by the first operation in the starting point (write 0). When the algorithm catch some 1s consecutive it rewrites from right to left every value from 0 to 1 including the starting value and the ends. I don't know if it's correct by this way, but i think that it works.

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

[ConstiDami]

blank: ' ' start state: moveendright table:

moveendright: [0, 1] : {R: moveendright} ' ': {L: moveleft}

moveleft: 0: {L: moveleft} 1: {write: 0, L: foundone} ' ' : {R: return}

foundone: 1 : {write: 0, L: foundtwo} 0 : {L: moveleft} ' ': {R: return}

foundtwo: 1 : {write: 0, L: foundthree} 0 : {L: moveleft} ' ': {R: return}

foundthree: [1, 0]: {write: 0, L: foundthree} ' ' : {R: returnfound}

return: [1, 0]: {write: 0, L: end}

returnfound: [1, 0]: {write: 1, L: end}

end:

[SarahTew]

Turing Machine Consecutive.pdf This is my table for finding consecutive 1s with a Turing machine. Like my chart for exercise 3, using this depends on being the head being able to move back to its starting position all at once at the end. I think there are ways to make the Turing machine do that (see my answer in exercise 3 for link) so if that's the case these instructions should work. The way it is written now I think it would work no matter how many cells followed after the head or what was printed on them. It would only read the first five after the initial start point.

I think these instructions are more efficient than those I made for exercise 3 (which I did first). For these ex. 2 instructions I got rid of some redundant states but couldn't figure out how to get rid of all of them (ie. the ones that that just tell you to keep reading right) without losing its ability to count just the first five cells.

[giorgiasampo]

[falcon1982]

CURR STATE	READ	WRITE	MOVE	NEXT STATE
OK
E	0	0	L	E
E	1	0	R	OK
F	0	1	R	G
F	1	1	R	G
G	0	0	R	G0
G	1	0	R	G1
G0	0	0	R	G00
G0	1	0	R	G01
G00	0	0	L	E
G00	1	0	R	G001
G01	0	0	L	E
G01	1	0	R	G011
G001	0	0	L	E
G001	1	0	R	G011
G011	0	0	L	E
G011	1	0	R	OK
G1	0	0	R	G10
G1	1	0	R	G011
G10	0	0	L	E
G10	1	0	R	G101
G101	0	0	R	E
G101	1	0	L	G011

[AlessandraFa]

I originally had another solution, but it didn’t have any stop condition and therefore wasn’t able to understand when to stop (once reached the 5th cell), so I wrote this one which is much longer, I couldn’t find a better one. In this case, the algorithm is also counting the steps and stops when it reaches the last cell (if the return conditions aren’t met before).

[gabrielefiorenza]

input : "011000" blank: "0" start state: start table: start: 0: { write: 1, R : A} A: 0: { write: 0, R : B} 1: { write: 1, R : B} B: 0: { write: 0, R : C} 1: { write: 1, R : C} C: 0: { write: 0, L : D} 1: { write: 1, R : G} D: 0: { write: 0, L : E} 1: { write: 1, L : E} E: 0: { write: 0, L : F} 1: { write: 1, L : F} F: 0: { write: 0, R : STOP} 1: { write: 0, R : STOP} G: 0: { write: 0, L : H} 1: { write: 1, R : M} H: 0: { write: 0, L : I} 1: { write: 1, L : I} I: 0: { write: 0, L : E} 1: { write: 1, L : L} L: 0: { write: 0, L : F} 1: { write: 0, L : STOP} M: 0: { write: 0, L : N} 1: { write: 1, L : STOP} N: 0: { write: 0, L : O} 1: { write: 0, L : O} O: 0: { write: 0, L : P} 1: { write: 0, L : P} P: 0: { write: 0, L : E} 1: { write: 1, L : STOP} STOP: