Lecture "Computability", exercise 3

[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 1s in any order, 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]

(With the input below, a zero is returned on the initial cell)

input: '001001'
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}
    [1]: {write: 0, R: findthird}
    [' ']: {L: getbacknotfound}

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

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

  end:

[edoardodalborgo]

In this solution the reasoning is inverted compared to the second exercise. I write 1 in the starting point and if the algorithm catch three different 1s values in three different states it ends, and the result is just printed at the starting point. If the algorithm catch some 0s and 1s but the 1s values aren't three, the algorithm rewrites every 1s values to 0, included the value of the starting point.

blank: [''] start state: A table: A: 0,1: {write 1, R: B} B: 0: {R: B} 1: {R: C} ['']: {L: E} C: 0: {R: C} 1: {R: D} ['']: {L: E} D: 0: {R: D} 1: {R: F} ['']: {L: E} E: 0: {L: E} 1: {write 0, 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: foundone} ' ': {R: return}

foundtwo: 1 : {write: 0, L: foundthree} 0 : {L: foundtwo} ' ': {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:

I used the same instructions as in ex.2, but instead of starting again with moveleft if the machine finds a 0, it stays in the state where the number of '1' found is 'stored' (in the name of the function).

[SarahTew]

Turing Machine non-consecutive 1s.pdf

My table assumes the head can move back to its original position in one movement which I think the Turing machine could do. I looked on stack exchange it said you could remove all the tape to the left of the cell where you want to write the answer, start running from there then send it back to the leftmost cell (aka the origin since the rest has been removed). That would work for my purposes. There could be other ways to do it as well; I don't really know.

I have tried so many different arrangements and so far I haven't found one it doesn't catch but please try it for yourself and let me know if the chart is easy to follow and gives you the right answers. Thanks!

[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
G1	0	0	R	G01
G1	1	0	R	G11
G01	0	0	R	G010
G01	1	0	R	G011
G00	0	0	L	E
G00	1	0	R	G010
G11	0	0	R	G110
G11	1	0	R	OK
G110	0	0	R	G1100
G110	1	0	R	OK
G1100	0	0	L	E
G1100	1	0	R	OK
G011	0	0	R	G1100
G011	1	0	R	OK
G001	0	0	L	E
G001	1	0	R	G1100

[LuisAmmi]

input: '010110' blank: '0' start state: start table: start: 0: { write: 1, R: pn } pn: 0: { write: 0, R: p0 } 1: { write: 0, R: p1 } p0: 0: { write: 0, R: p00 } 1: { write: 0, R: p01 } p1: 0: { write: 0, R: p10 } 1: { write: 0, R: p11 } p00: 0: { write: 0, L: fail } 1: { write: 0, R: p001 } p01: 0: { write: 0, R: p001 } 1: { write: 0, R: p011 } p10: 0: { write: 0, R: p001 } 1: { write: 0, R: p011 } p11: 0: { write: 0, R: p011 } 1: { write: 0, L: stop } p001: 0: { write: 0, L: fail } 1: { write: 0, R: p0011 } p011: 0: { write: 0, R: p0011 } 1: { write: 0, L: stop } p0011: 0: { write: 0, L: fail } 1: { write: 0, L: stop } fail: 0: { write: 0, L: fail } 1: { write: 0, L: stop } stop:

[gabrielefiorenza]

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