Lecture "Computability", exercise 3 about 2020-2021 HOT 7 OPEN

(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:

from 2020-2021.

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

from 2020-2021.

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).

from 2020-2021.

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!

from 2020-2021.

from 2020-2021.

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:

from 2020-2021.

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:

from 2020-2021.