Lecture "Computability", exercise 2

[essepuntato]

Consider an algorithm that takes as input a 0-1 sequence of exactly five symbols and returns 1 if the sequence contains at least three consecutive 1s, and returns 0 otherwise. Implement the algorithm with a Turing machine, where the cell corresponding 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.

[vattelalberto]

I don't know if it is possible to implement the machine in a more compact way, here is the turingmachine.io code that i created that can solve the problem for any 5-digit input, shifting the input number to the right and displaying the result in the starting cell. My implementations starts by copying the five digits one cell to the right, and then work backwards to check if there are three consecutive 1s.

input: '00000'
blank: '0'
start state: start
end state: end
table:
  start:
    '0': {R: zero_1}
    '1': {write: 0, R: one_1}
  zero_1:
    '0': {write: 0, R: zero_2}
    '1': {write: 0, R: one_2}
  one_1:
    '0': {write: 1, R: zero_2}
    '1': {write: 1, R: one_2}
  zero_2:
    '0': {write: 0, R: zero_3}
    '1': {write: 0, R: one_3}
  one_2:
    '0': {write: 1, R: zero_3}
    '1': {write: 1, R: one_3}
  zero_3:
    '0': {write: 0, R: zero_4}
    '1': {write: 0, R: one_4}
  one_3:
    '0': {write: 1, R: zero_4}
    '1': {write: 1, R: one_4}
  zero_4:
    '0': {write: 0, R: zero_5}
    '1': {write: 1, R: one_5}
  one_4:
    '0': {write: 1, R: zero_5}
    '1': {write: 1, R: one_5}
  zero_5:
    [0, 1]: {write: 0, L: 5_Z}
  one_5:
    [0, 1]: {write: 1, L: 5_1}
  5_Z:
    '0': {L: 4_Z}
    '1': {L: 4_1}
  5_1:
    '0': {L: 4_Z}
    '1': {L: 4_11}
  4_Z:
    '0': {L: 3_Z}
    '1': {L: 3_1}
  4_1:
    '0': {L: 3_Z}
    '1': {L: 3_11}
  4_11:
    '0': {L: 3_Z}
    '1': {L: 3_111}
  3_Z:
    [0,1]: {L: 2_Z}
  3_1:
    '0': {L: 2_Z}
    '1': {L: 2_11}
  3_11:
    '0': {L: 2_Z}
    '1': {L: 2_111}
  3_111:
    [0,1]: {L: 2_111}
  2_Z:
    [0,1]: {L: end}
  2_11:
    '0': {L: end}
    '1': {L: 1_111}
  2_111:
    [0,1]: {L: 1_111}
  1_111:
    [0,1]: {write: 1, L: end}
  end:

[valetedd]

table:

  start:
    ' ': {R: start}
    0: {R: check}
    1: {R: check_2}

  check:
    0: {R: check}
    1: {R: check_2}
    ' ': {L: return_n}
  check_2:
    0: {R: check}
    1: {R: check_3}
    ' ': {L: return_n}
  check_3:
    0: {R: check}
    1: {L: return_y}
    ' ': {L: return_n}
  return_n:
    [0,1]: {L: return_n}
    ' ': {write: 0, L: end}

  return_y:
    [0,1]: {L: return_y}
    ' ': {write: 1, L: end}
  end: ``` 

[qwindici]

In my code q(n) identifies how many 1s have been counted. When a 0 is encountered it goes back to q0 since the sequence of 1s should restart. I used dashes '-' (not sure this is allowed though) to identify the start and the end of the sequence in order to print the result.

input: ' 00011'
blank: ' '
start state: start
table:
  start:
    ' ': {write: '-', R: q0}
  q0:
    ' ': {write: '-', L: return_0}
    0: {R}
    1: {R: q1}
  q1:
    0: {R: q0}
    1: {R: q2}
    ' ': {L: return_0}
  q2:
    0: {R: q0}
    1: {R: return_1}
    ' ': {L: return_0}
  return_1:
    [1, 0]: {L}
    '-': {write: 1, L: end}
  return_0: 
    [1, 0]: {L}
    '-': {write: 0, L: end}
  end:

Update -- Managed to rewrite it without using dashes:

input: ' 11111'
blank: ' '
start state: start
table:
  start:
    ' ': {R: q0}
  q0:
    ' ': {L: return_0}
    0: {R}
    1: {R: q1}
  q1:
    0: {R: q0}
    1: {R: q2}
    ' ': {L: return_0}
  q2:
    0: {R: q0}
    1: {L: return_1}
    ' ': {L: return_0}
  return_1:
    [1, 0]: {L}
    ' ': {write: 1, L: end}
  return_0: 
    [1, 0]: {L}
    ' ': {write: 0, L: end}
  end:

[Liber-R]

Reformulation without blank symbols in the instructions

[ThIheb]

The initial sequence checks the numbers from left to right, if it finds three consecutive '1' it runs back to the starting position with the help of R1 otherwise it keeps checking if it finds a blank space or 0 it returns R0 which gives us 0

[rufferbaraldi]

I couldn't programm the part "where the cell corresponding to the starting position of the head is where the final result must be stored.", But it works well despite this missing command.

input: '00111' or '01110' or '11100' or any other haha blank: '0' start state: A table: A: [0]: {write: 0, R: B} [1]: {write: 0, R: C} B: [0]: {write: 0, R: D} [1]: {write: 0, R: E} C: [0]: {write: 0, R: D} [1]: {write: 0, R: F} D: [0]: {write: 0, R: End} [1]: {write: 0, R: G} E: [0]: {write: 0, R: End} [1]: {write: 0, R: H} F: [0]: {write: 0, R: End} [1]: {write: 1, R: End} G: [0]: {write: 0, R: End} [1]: {write: 0, R: J} H: [0]: {write: 0, R: End} [1]: {write: 1, R: End} J: [0]: {write: 0, R: End} [1]: {write: 1, R: End} End: [0,1]: {write: 0, R}

[essepuntato]

Hi all, thanks for your takes. Just a note for all: remember that you are entitled to use only two symbols in the Turing Machines, i.e. 0 and 1, so the blank symbol should be 0. Using, as a blank symbol, the space character means to use three symbols in the Turing Machine...

[frammenti]

Start state: Start End state: End

Current state	Tape symbol	Write symbol	Move head	Next state
Start	1 or 0	0	R	First
First	1		R	Second1
	0	1	R	Second0
Second1	1		R	Third1
	0	1	R	Second0
Third1	1		L	Result
	0		L	End
Second0	1		R	Second1
	0	1	R	Third0
Third0	1		R	Second1
	0		L	End
Result	1		L	Result
	0	1	R	End
End

# search for three consecutive 1s in 5 digit sequence
input: '011011' # as an example
blank: '0'
start state: Start
table:
  # initialize result cell to 0
  Start:
    [1,0]: {write: 0, R: First}
  # if 1 search for second 1, if 0 search for second 0
  First:
    [1]: {R: Second1}
    [0]: {write: 1, R: Second0}
  # if 1 search for third 1, if 0 search for second 0
  Second1:
    [1]: {R: Third1}
    [0]: {write: 1, R: Second0}
  # if 1 print result, if 0 end
  # (with 1/2 digits left, impossible to find three 1s)
  Third1:
    [1]: {L: Result}
    [0]: {L: End}
  # if 1 search for second 1, if 0 search for third 0
  Second0:
    [1]: {R: Second1}
    [0]: {write: 1, R: Third0}
  # if 1 search for second 1, if 0 end
  Third0:
    [1]: {R: Second1}
    [0]: {L: End}
  # positive result: go backwards until 0 (starting cell) and print 1
  Result:
    [1]: {L: Result}
    [0]: {write: 1, R: End}
  End:

Turing machine visualization

[valetedd]

Improving on previous attempt, which used blanks:

start state: start
table:

  start:
    0: {R: check_1}

  check_1:
    0: {write: 1, R: check_2}
    1: {R: ok_1}

  check_2:
    0: {write: 1, R: check_3}
    1: {R: ok_1}

  check_3:
    0: {L: end}
    1: {R: ok_1}

  ok_1:
    0: {write: 1, R: check_3}
    1: {R: ok_2}

  ok_2:
    0: {L: end}
    1: {R: ok_3}

  ok_3:
    [0, 1]: {L: return_y} 

  return_y:
    1: {L: return_y}
    0: {write: 1, R: end}

  end: 

[simocasaz]

input: '010011'
blank: '0'
start state: A
table:
  A:
    0: { write: 0, R: B }

  B:
    0: { write: 1, R: C }
    1: { write: 1, R: oneconsecutive }

  C:
    0: { write: 1, R: D }
    1: { write: 1, R: oneconsecutive }

  D:
    0: { write: 1, R: E }
    1: { write: 1, R: oneconsecutive }

  E:
    0: { write: 1, R: F }
    1: { write: 1, R: oneconsecutive }

  F:
    0: { write: 1, L: end }
    1: { write: 1, L: end }

  oneconsecutive:
    0: { write: 1, R: D }
    1: { write: 1, R: twoconsecutives }

  twoconsecutives:
    0: { write: 1, R: E }
    1: { write: 1, L: yesresult }

  yesresult:
    1: { write: 1, L: yesresult }
    0: { write: 1, L: end }

  end:

[CarlaMenegat]

A new tentative of solution: