Lecture "Computability", exercise 3

[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 1s in any order, while it 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've slightly tweaked the machine used in exercise 2

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_1}
    '1': {L: 4_11}
  4_Z:
    '0': {L: 3_Z}
    '1': {L: 3_1}
  4_1:
    '0': {L: 3_1}
    '1': {L: 3_11}
  4_11:
    '0': {L: 3_11}
    '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_11}
    '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_2}
    1: {R: check_3}
    ' ': {L: return_n}

  check_3:
    0: {R: check_3}
    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]

Update -- Without using dashes as in the first try:

input: ' 10001'
blank: ' '
start state: start
table:
  start:
    ' ': {write: ' ', R: s0}
  s0:
   1: {R: s1}
   0: {R}
   ' ': {L: return_0}
  s1:
   1: {R: s2}
   0: {R}
   ' ': {L: return_0}
  s2: 
    1: {L: return_1}
    0: {R}
    ' ': {L: return_0}
  return_1: 
    [0, 1]: {L}
    ' ': {write: 1, L: end}
  return_0:
    [0, 1]: {L}
    ' ': {write: 0, L: end}
  end: 

---

As in the second exercise, I use the s(n) to indicate the counting of 1s. However, in this case, instead of going to state 0 when a 0 is found, the machine stays in the same state. As before, I used dashes to get where the sequence ends in order to print the result.

input: ' 01100'
blank: ' '
start state: start
table:
  start:
    ' ': {write: '-', R: s0}
  s0:
   1: {R: s1}
   0: {R}
   ' ': {L: return_0}
  s1:
   1: {R: s2}
   0: {R}
   ' ': {L: return_0}
  s2: 
    1: {R: return_1}
    0: {R}
    ' ': {L: return_0}
  return_1: 
    [0, 1]: {L}
    '-': {write: 1, L: end}
  return_0:
    [0, 1]: {L}
    '-': {write: 0, L: end}
  end:

[Liber-R]

Reformulation without blank symbols in the instructions.

[ThIheb]

Same principle as exercise 2

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

[CarlaMenegat]

[valetedd]

Second attempt, w/o blanks

start state: start
table:

  start:
    0: {R: check_p1}

    # checking first three positions, count=0

  check_p1:
    0: {write: 1, R: check_p2}
    1: {R: check1_p2}
  check_p2:
    0: {write: 1, R: check_p3}
    1: {R: check1_p3}
  check_p3:
    0: {R: end}
    1: {R: check1_p4}

    # checking the three positions in the middle, count=1

  check1_p2:
    0: {write: 1, R: check1_p3}
    1: {R: check2_p3}

  check1_p3:
    0: {write: 1, R: check1_p4}
    1: {R: check2_p4}

  check1_p4:
    0: {R: end}
    1: {R: check2_p5}

  # checking last three positions, count=2

  check2_p3:
    0: {write: 1, R: check2_p4}
    1: {R: return_y}
  check2_p4:
    0: {write: 1, R: check2_p5}
    1: {R: return_y}
  check2_p5:
    0: {R: end}
    1: {L: return_y}

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

[frammenti]

Start state: start End state: stop

Current state	Tape symbol	Write symbol	Move head	Next state
start	1 or 0	0	R	0-0
0-0	1		R	1-0
	0	1	R	0-1
1-0	1		R	2-0
	0	1	R	1-1
2-0	1		L	result
	0	1	R	2-1
0-1	1		R	1-1
	0	1	R	0-2
0-2	1		R	1-2
	0		L	stop
1-1	1		R	2-1
	0	1	R	1-2
2-1	1		L	result
	0	1	R	2-2
1-2	1		R	2-2
	0		L	stop
2-2	1		L	result
	0		L	stop
result	1		L	result
	0	1	R	stop
stop

# search for at least three 1s in any order in 5 digit sequence
input: '001101' # as an example
blank: '0'
start state: start
table:
  # initialize result cell to 0
  start:
    [1,0]: {write: 0, R: 0-0}
  # state = A-B where A is the n. of occurrences of 1s so far and B is the same for 0s
  # all 1s first (fastest route to result = 1)
  0-0:
    [1]: {R: 1-0}
    [0]: {write: 1, R: 0-1}
  1-0:
    [1]: {R: 2-0}
    [0]: {write: 1, R: 1-1}
  2-0:
    [1]: {L: result}
    [0]: {write: 1, R: 2-1}
  # all 0s first (fastest route to result = 0)
  0-1:
    [1]: {R: 1-1}
    [0]: {write: 1, R: 0-2}
  0-2:
    [1]: {R: 1-2}
    [0]: {L: stop}
  # mixed occurrences of 1s and 0s
  1-1:
    [1]: {R: 2-1}
    [0]: {write: 1, R: 1-2}
  2-1:
    [1]: {L: result}
    [0]: {write: 1, R: 2-2}
  1-2:
    [1]: {R: 2-2}
    [0]: {L: stop}
  2-2:
    [1]: {L: result}
    [0]: {L: stop}
  # positive result: go backwards until 0 (starting cell) and print 1
  result:
    [1]: {L: result}
    [0]: {write: 1, R: stop}
  stop:

Turing machine visualization

[simocasaz]

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

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

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

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

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

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

  D1:
    0: { write: 1, R: E1 }
    1: { write: 1, R: twoones }

  E1:
    0: { write: 1, R: F1 }
    1: { write: 1, R: twoones }

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

  E2:
    0: { write: 1, R: F2 }
    1: { write: 1, L: yesresult }

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

  oneone:
    0: { write: 1, R: D1 }
    1: { write: 1, R: twoones }

  twoones:
    0: { write: 1, R: E2 }
    1: { write: 1, L: yesresult }

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

  end: