Lecture "Computability", exercise 2

[essepuntato]

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

[ilsamoano]

2 questions about the above:

A] the algorithm should be able to solve all the possible 0-1 sequences?
i.e. 11100 00111 10101 01110 etc?
or we must pick one of the above only?

B] do we have to have the algorithm write the result in the starting cell?
if I input 5 symbols in http://turingmachine.io/ , the starting position is the first one of the five symbols: so I'll have 4 inputs following the starting position, while in the exercise description seems that the inputs are 6 in total: starting position + 5 five cells following

If we can pick only one sequence at time as an input and we must write the output on the left side of the first input (6 inputs)
input: "11100"
blank: ' '
start state: A
table:
A:
1: {R: B}
0: {R: B}
B:
1: {R: C}
0: {R: C}
C:
1: {L: D}
0: {R: A}
D:
1: {L: E}
E:
1: {L: F}
F:
' ': {write: 1, R: done}

done:

If we can pick only one sequence at time as an input and we must write the output on the first input (5 inputs)
`input: "11100"
blank: ' '
start state: A
table:
A:
1: {R: B}
0: {R: B}
B:
1: {R: C}
0: {R: C}
C:
1: {L: D}
0: {R: A}
D:
1: {L: E}
E:
1: {write: 1,L: end}

end:`

p.s. I spent a considerable amount of time trying to set an algorithm for multiple 1-0 sequences of five inputs, at max I was able to cover a couple of possibilities.. if this is the request and someone wants to share with me how to do it, it would be really appreciated :)

[federicabologna]

Hi everyone!

I was asking myself the same thing you mentioned in A]. I would be very interested in knowing how to build and implement such an algorithm. @essepuntato could you please explain it class or at another more convenient time?
In case we had to pick only one possibility, here's what I did:

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

Hope that's ok!
See you in class :)

[giuliapl]

blank: '0'
start state: First
table:

FIRST:
     1: {write: 1, R, UA’_FIRST}
     0: {write: 1, R, SECOND}
UA’_FIRST
     1: {write: 1, R, UA’’_FIRST}
     0: {write: 1, R, UA’_THIRD}
UA’_THIRD
     1: {write: 1, R, UA’’_THIRD}
     0: {write: 1, R, END}
UA’’_THIRD
     1: {write: 1, R, UA’’’}
     0: {write: 1, R, END}
UA’’’
     1: {write: 1, L, ACCEPT}
     0: {write: 1, L, END}
ACCEPT
     1: {write: 1, L, ACCEPT}
     0: {write: 1m L, END}
SECOND
     1: { write: 1, R, UA’_SECOND}
     0: {write: 1, R, UA’_THIRD}
UA’_SECOND
     1: {write: 1, R, UA’’_SECOND}
     0: {write: 1, R, END}
UA’’_SECOND
     1: {write: 1, R, UA’’’}
     0: {write: 1, R, END}
UA’’_FIRST
     1: {write: 1, R, UA’’’}
     0: {write: 1, R, END}

[mangiafrangette]

I came up with two different solutions (they work with any given input): the first makes the assumption of having a blank cell at the starting position pointed by the head (using an extra blank symbol at the start of the input), the second one only uses 0 and 1 and shifts the cells to the right before running the algorithm.
First solution:

input: ' 00111'
blank: ' '
start state: start
table:
  start:
    [0,1,' ']: {R: count0}
  count0:
    1: {R: count1}
    0: {R: count0}
    ' ': {L: fail}
  count1:
    1: {R: count2}
    0: {R: count0}
    ' ': {L: fail}
  count2:
    1: {L: success}
    0: {R: count0}
    ' ': {L: fail}
  success:
    ' ': {write: 1, L: return}
    [0,1]: {L: success}
  fail:
    ' ': {write: 0, L: return}
    [0,1]: {L: fail}
  return:

Second solution:

input: '00111'
blank: ' '
start state: start
table:
  start:
    0: {write: ' ', R: copy0}
    1: {write: ' ', R: copy1}
  copy0:
    0: {write: 0, R: copy0}
    1: {write: 0, R: copy1}
    ' ': {write: 0, L: count0}
  copy1:
    0: {write: 1, R: copy0}
    1: {write: 1, R: copy1}
    ' ': {write: 1, L: count1}
  count0:
    0: {write: 0, L: count0}
    1: {write: 1, L: count1}
    ' ': {write: '0', L: return}
  count1:
    0: {write: 0, L: count0}
    1: {write: 1, L: count2}
    ' ': {write: '0', L: return}
  count2:
    0: {write: 0, L: count0}
    1: {write: 1, L: success}
    ' ': {write: '1', L: return}
  success:
    [0,1]: {L: success}
    ' ': {write: 1, L: return}
  return:

[MattiaSpadoni]

2 different ways:
The first one is developed on my own, after a discussion with @mangiafrangette I understand that my code is too long and too complicated.
So I've tried to simplify it in the second way. Thanks to Francesca for her advices

input: ' 10111'
blank: ' '
start state: a
table:
a:
' ': {R: a1}
a1:
1: {R: b2}
0: {R: b1}
b1:
1: {R: c3}
0: {R: c1}
c1:
1: {R: d2}
0: {R: x}
b2:
0: {R: c1}
1: {R: c2}
c2:
0: {L: x}
1: {L: y}
c3:
0: {L: x}
1: {R: d3}
d3:
0: {L: x}
1: {L: y}
d2:
0: {L: x}
1: {R: e2}
e2:
0: {R: x}
1: {L: y}
x:
[0,1]: {L: x}
' ': {write: 0, L: end}
y:
[0,1]: {L: y}
' ': {write: 1, L: end}
end:

Way 2

input: ' 01101'
blank: ' '
start state: A
table:
A:
[0,1,' ']: {R: b}
b:
1: {R: c}
0: {R: b}
' ': {L: x}
c:
1: {R: d}
0: {R: b}
d:
1: {L: y}
0: {R: b}
y:
' ': {write: 1, L: return}
[0,1]: {L: y}
x:
' ': {write: 0, L: return}
[0,1]: {L: x}
return:

[friendlynihilist]

This solution is based on the approach that if the first (or the second) value '1' is followed by the value '0' in the next cell, then it couldn't be possible to have three 1's in a row (in a five digits context). That's the reason why it doesn't need to always scan to the rightmost cell to return 0.

The output of the first is '0':

input: ' 01101'
blank: ' '
start state: start
table:
  start:
    1: {R: scan}
    0: {R: scan}
    ' ': {R: scan}
  scan:
    0: R
    1: {R: value1}
  value1:
    0: {R: retneg}
    1: {R: value2}
  value2:
    0: {R: retneg}
    1: {L: retpos}
  retpos:
    0: L
    1: L
    ' ': {write: 1, L: done}
  retneg:
    0: L
    1: L
    ' ': {write: 0, L: done}
  done:

While the output of the second is '1':

input: ' 00111'
blank: ' '
start state: start
table:
  start:
    1: {R: scan}
    0: {R: scan}
    ' ': {R: scan}
  scan:
    0: R
    1: {R: value1}
  value1:
    0: {R: retneg}
    1: {R: value2}
  value2:
    0: {R: retneg}
    1: {L: retpos}
  retpos:
    0: L
    1: L
    ' ': {write: 1, L: done}
  retneg:
    0: L
    1: L
    ' ': {write: 0, L: done}
  done:

[delfimpandiani]

I struggled with this one and decided to check out my classmates' answers;

I came up with two different solutions (they work with any given input): the first makes the assumption of having a blank cell at the starting position pointed by the head (using an extra blank symbol at the start of the input), the second one only uses 0 and 1 and shifts the cells to the right before running the algorithm.
First solution:

input: ' 00111'
blank: ' '
start state: start
table:
  start:
    [0,1,' ']: {R: count0}
  count0:
    1: {R: count1}
    0: {R: count0}
    ' ': {L: fail}
  count1:
    1: {R: count2}
    0: {R: count0}
    ' ': {L: fail}
  count2:
    1: {L: success}
    0: {R: count0}
    ' ': {L: fail}
  success:
    ' ': {write: 1, L: return}
    [0,1]: {L: success}
  fail:
    ' ': {write: 0, L: return}
    [0,1]: {L: fail}
  return:

Second solution:

input: '00111'
blank: ' '
start state: start
table:
  start:
    0: {write: ' ', R: copy0}
    1: {write: ' ', R: copy1}
  copy0:
    0: {write: 0, R: copy0}
    1: {write: 0, R: copy1}
    ' ': {write: 0, L: count0}
  copy1:
    0: {write: 1, R: copy0}
    1: {write: 1, R: copy1}
    ' ': {write: 1, L: count1}
  count0:
    0: {write: 0, L: count0}
    1: {write: 1, L: count1}
    ' ': {write: '0', L: return}
  count1:
    0: {write: 0, L: count0}
    1: {write: 1, L: count2}
    ' ': {write: '0', L: return}
  count2:
    0: {write: 0, L: count0}
    1: {write: 1, L: success}
    ' ': {write: '1', L: return}
  success:
    [0,1]: {L: success}
    ' ': {write: 1, L: return}
  return:

@mangiafrangette this is genius! Both of them. The idea of the count states really makes things so much easier. I especially find the second solution ingenious, with the separate copy and count states, and the count state being "backwards" (from L to R). It took me a while (trying different inputs) to fully understand its workings, but now I do and love it!

[SeverinJB]

Note:
I read the lecture notes after doing the exercise. Hence, the following solution was created without the webpage http://turingmachine.io. Also, the following solution does not use blank fields as input. As the examples in class, the solution is based on 0s and 1s as possible inputs. The solution works for every input: 00000 – 11111

Initial state: A
Successful ending: E
Unsuccessful ending: F

Issue: Machine does not stop, but continues writing the result in an endless loop.
A possible solution to issue: Introducing as many states as necessary to return "home".

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	0	R	B	0	R	G	0	R	I
1	0	R	B	0	R	C	0	R	D
Tape symbol	Current state (D)			Current state (E)			Current state (F)
0	0	L	F	1	L	E	0	L	F
1	1	L	E	1	L	E	0	L	F
Tape symbol	Current state (G)			Current state (H)			Current state (I)
0	0	R	I	0	L	F	0	L	F
1	0	R	H	0	R	D	0	R	H

[HiImBono]

I tried to write a solution to all 5 digit combinations in the most abstract way. I do not use any ingenious techniques to minimize computation time but at least I feel like it would provide
the correct solution to all combinations. Also I assumed a total of 5 digits not 6.

Note that I wrote the initial digit combination the machine has read so far after the percentage sign. In this way one can see what the machine has seen so far.
I make every digit the machine has seen into a 1. Everytime the machine has seen three 1's in a row it is done (I dont know how the machine terminates i maybe thought jumping to an empty state 'DONE')
When the machine reaches a point where there is not more possibility to have three consecutive 1's the machine stwitches to on of the four END states depending on the current state.
The END states guide the machine to make its way back to the starting digit to turn it into a 0.

input: ..... (5 random digits either 1 or 0)
start state: A
table:
A:
0: { write: 1, R: B1} % 0
1: { write: 1, R: B2} % 1
B1:
0: { write: 1, R: C1} % 00
1: { write: 1, R: C2} % 01
B2:
0: { write: 1, R: C3} % 10
1: { write: 1, R: C4} % 11
C1:
0: { L: END2} % 000
1: { write: 1, R: D1} % 001
C2:
0: { L: END2} % 010
1: { write: 1, R: D2} % 011
C3:
0: { L: END2} % 100
1: { write: 1, R: D3} % 101
C4:
0: { L: END2} % 110
1: { L: DONE} % 111
D1:
0: { L: END3} % 0010
1: { write: 1, R: E1} % 0011
D2:
0: { L: END3} % 0110
1: { L: DONE} % 0111
D3:
0: { L: END3} % 1010
1: { write: 1, R: E2} % 1011
E1:
0: { L: END4} % 00110
1: { L: DONE} % 00111
E2:
0: { L: END4} % 10110
1: { L: DONE} % 10111
END4:
1: { L: END3}
END3:
1: { L: END2}
END2:
1: { L: END1}
END1:
1: { write:0, L: DONE}
DONE:
empty state

[lisasiurina]

input: '00111'
blank: ' '
start state: A
table:
A:
[0,1,' ']: {R: b}

B:
1: {R:C}
0: {R:B}

C:
1: {R:D}
0: {R:B}

D:
1: {L:y}
0: {R:B}

y:

' ‘ : {write: 1, L: return}
[0,1]: {L:y}

x:
' ‘ : {write: O, L: return}
[0,1]: {L:x}

[essepuntato]

Hi all,

As you already know, there are plenty of possible different solutions to this problem, and you guys have already provide different working approaches here – thanks a lot for this!

I'm providing the solution to this exercise I've sketched during the previous lecture so as to be reused in the Turing Machine Visualization tool for testing it. Remember that when one do not specify any "write" instruction implicitly means that the head will write on the tape exactly the same symbol that is already written there.

input: '011101'
blank: '0'
start state: start
table:
  start: 
    [0,1]: { R: a }
  a:
    1: { R: a1 }
    0: { R: a0 }
  a1:
    1: { R: a11 }
    0: { R: a10 }
  a0:
    1: { R: a10 }
    0: { R: a00 }
  a11:
    1: { L: success3 }
    0: { R: a110 }
  a10:
    1: { R: a110 }
    0: { R: a100 }
  a00:
    1: { R: a100 }
    0: { L: stop }
  a110:
    1: { L: success4 }
    0: { R: a1100 }
  a100:
    1: { R: a1100 }
    0: { L: stop }
  a1100:
    1: { L: success5 }
    0: { L: stop }
  
  success5:
    [0,1]: { L: success4 }
  success4:
    [0,1]: { L: success3 }
  success3:
    [0,1]: { L: success2 }
  success2:
    [0,1]: { L: success1 }
  success1:
    [0,1]: { write: 1, L: stop }
  
  stop: