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.

[sntcristian]

A: 0 or 1: {- R B} B: 0 or 1: {- R C} C: 0 or 1: {- R D} D: 0 or 1: {- R E} E: 0 or 1: {- R F} F: 0: {- L I} 1: {- L G} G: 0:{- L N} 1:{- L H } H: 1:{- L Z} 0:{- L X} I: 0:{- L N} 1:{- L L} L: 0:{- L X} 1:{- L M} M: 0:{- L U} 1:{- L V} N: 0: {- L X} 1: {- L O} O: 0:{- L U} 1:{- L P} P: 0:{- L W} 1:{- L Y} Z: 0 or 1:{- L V} X: 0 or 1:{- L U } V: 0 or 1:{- L Y } U: 0 or 1:{- L W} Y: 0 or 1:{1 - T} W: 0 or 1:{0 - T} T:

[ariannamorettj]

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.

Possible Outputs: 1--> if there is inside a series of at least 3 consecutive 1s 0 --> otherwise Blank: 0 Input: series of five symbols 0 or 1 Start: in the cell at the immediate left of the first cell of the five containing the input.

Current state	Tape symbol	Write symbol	Move head	Next state
A	0 or 1	0	Right	B
B	1	/	Right	C
	0	/	Right	D
C	1	/	Right	E
	0	/	Right	F
D	1	/	Right	G
	0	/	Right	F
E	1	/	Left	H
	0	/	Left	N
F	1	/	right	Q
	0	/	Left	N
G	1	/	Right	R
	0	/	Left	N
H	1	/	Left	I
	0	/	Left	I
I	0	/	Left	L
	1	/	Left	L
L	0/1	1	Left	M
M
N	0/1	/	Left	O
O	0/1	/	Left	P
P	0/1	0	Left	M
Q	1	/	Right	T
	0	/	Left	S
S	0/1	/	Left	N
R	1	/	Left	U
	0	/	Left	S
T	1	/	Left	V
	0	/	Left	W
U	1/0	/	Left	H
V	1/0	/	Left	U
W	1/0	/	Left	S

Before writing the table, I had drawn a map assuming that, since (2^5) - 8 = 24 (over 32) combinations of 0s and 1s lead to store 0 as output in the first cell at the left of the input series, maybe it could be useful to set "0" as default value in this first cell, so that only in the 8 cases ( 11111/ 11110 / 11100 / 01110 / 01111 / 00111 / 10111 / 11101) in which the output is 1 the machine would have come back to that position to change the symbol from 0 to 1. Anyway, I was quite sceptical about this process, so I tried in another way (which is the final one I wrote in the table).

[NoonShin]

The following solution is provided assuming that empty cells exist in the alphabet and that all the cells, excepting the first 6 (first head position and the following input values), are empty.

[FrancescoFernicola]

For some reason turingmachine.io displays a "Syntax Error: duplicated mapping key" message so I can't play out the algorithm but I can't really find the error. It should still work though.

blank: '0' start state: A table:

A: [0,1]: {write: 0, R: B}

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

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

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

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

F: '0': {write: 0, L: I} '1': {write: 1, L: G}

G: '0': {write: 0, L: N} '1': {write: 1, L: H}

H: '0': {write: 0, L: Q} '1': {write: 1, L: J}

I: '0': {write: 0, L: N} '1': {write: 1, L: L}

J: '0': {write: 0, L: K} '1': {write: 1, L: K}

K: '0': {write: 0, L: S} '1': {write: 1, L: S}

L: '0': {write: 0, L: Q} '1': {write: 1, L: M}

M:
'0': {write: 0, L: R} '1': {write: 1, L: K}

N: '0': {write: 0, L: Q} '1': {write: 1, L: O}

O: '0': {write: 0, L: R} '1': {write: 1, L: P}

P: '0': {write: 0, L: T} '1': {write: 1, L: S}

Q:
'0': {write: 0, L: R} '1': {write: 1, L: R}

R:
'0': {write: 0, L: T} '1': {write: 1, L: T}

S: [0,1]: {write: 1, L: done}

T: [0,1]: {write: 0, L: done}

done:

[arcangelo7]

I've simply understood Nooshin solution and translated it into a table of instruction and a Turing Machine Visualization. You can find the code to try yourself here: https://gist.github.com/arcangelo7/0f7d37ce1de650818e46566a560796ab.

[noreanystrom]

After a lot of thinking I came up with below solution. (The numbers on the left side of the chart is my mental process, the potential incoming sequence > new sequence)

[essepuntato]

Hi guys,

Here is my solution, that can be run in the Turing Machine Visualisation Tool, if you want to see what happens.

input: '010111'
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: p00 }
    1: { write: 0, R: p11 }
  p00:
    0: { write: 0, L: fail }
    1: { write: 0, R: p001 }
  p01:
    0: { write: 0, L: fail }
    1: { write: 0, R: p011 }
  p11:
    0: { write: 0, L: fail }
    1: { write: 0, L: stop }
  p001:
    0: { write: 0, L: fail }
    1: { write: 0, R: p0011 }
  p011:
    0: { write: 0, L: fail }
    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:

The structure of the solution I've proposed is as follows: to count how many 1s have been processed in a row and, in case this number is lesser than 3, then move the head back to the first cell to write 0, otherwise, it will leave the 1 set in the very first operation of the Machine.

The last thing: @FrancescoFernicola the problem with the syntax error is related to some wrong indent.

PS: The solution to this exercise I've proposed initially has been just fixed (on October 28, 2019) to be compliant with the text fo the exercise that asks to have a sequence of three consecutive 1s to return 1. In fact, the solution proposed before returned 1 if the input sequence contains three 1s independently from the order they appear in the sequence. This latter exercise/solution is now available in a new issue, that will be also added to lecture notes online. Apologies for the inconvenience.