Lecture "Computability", exercise 3

[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 1s in any order while 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.

[ManueleVeggi]

I followed a very similar approach to the one implemented in the previous exercise, creating an Excel visualisation so as to streamline the general algorithm. The visualisation on "Turing machine Visualisation" should be the following:

input: '000111'
blank: '0'
start state: start
table:
  start:
    0: { write: 1, R: hn }

  hn:
    0: { write: 0, R: h0 }
    1: { write: 0, R: h1 }

  h0:
    0: { write: 0, R: h00 }
    1: { write: 0, R: h01 }
  h1:
    0: { write: 0, R: h00 }
    1: { write: 0, R: h11 }

  h00:
    0: { write: 0, L: unfit }
    1: { write: 0, R: h001 } 
  h01:
    0: { write: 0, L: h001 }
    1: { write: 0, R: h011 }
  h10:
    0: { write: 0, L: h001 }
    1: { write: 0, L: h101 }
  h11:
    0: { write: 0, L: h110 }
    1: { write: 0, L: end }

  h001:
    0: { write: 0, L: unfit }
    1: { write: 0, R: h0011 }
  h011:
    0: { write: 0, L: h0011 }
    1: { write: 0, L: end }
  h101:
    0: { write: 0, R: h0011 }
    1: { write: 0, R: end}
  h110:
    0: { write: 0, R: unfit }
    1: { write: 0, R: h0011 }

  h0011:
    0: { write: 0, L: unfit }
    1: { write: 0, L: end }

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

[tommasobattisti]

input: '010110' blank: '0' start state: start table: start: 0: { write: 1, R: S } S: 0: { write: 0, R: S0 } 1: { write: 0, R: S1 } S0: 0: { write: 0, R: S00 } 1: { write: 0, R: S01 } S1: 0: { write: 0, R: S10 } 1: { write: 0, R: S11 } S00: 0: { write: 0, L: fail } 1: { write: 0, R: S001 } S01: 0: { write: 0, L: S010 } 1: { write: 0, R: S011 } S10: 0: { write: 0, L: S100 } 1: { write: 0, R: S101 } S11: 0: { write: 0, L: S110 } 1: { write: 0, R: stop } S001: 0: { write: 0, L: fail } 1: { write: 0, R: S0011 } S010: 0: { write: 0, L: fail } 1: { write: 0, R: S0101 } S011: 0: { write: 0, L: fail } 1: { write: 0, R: stop } S100: 0: { write: 0, L: fail } 1: { write: 0, R: S1001 } S101: 0: { write: 0, L: S1010 } 1: { write: 0, R: stop } S110: 0: { write: 0, L: S1100 } 1: { write: 0, R: stop } S0011: 0: { write: 0, L: fail } 1: { write: 0, R: stop } S0101: 0: { write: 0, L: fail } 1: { write: 0, R: stop } S1001: 0: { write: 0, L: fail } 1: { write: 0, R: stop } S1010: 0: { write: 0, L: fail } 1: { write: 0, R: stop } S1100: 0: { write: 0, L: fail } 1: { write: 0, R: stop } fail: 0: { write: 0, L: fail } 1: { write: 0, L: stop } stop:

[federicabonifazi]

Same as the previous exercise, this should go as follows:

input: 'x10011'
blank: ' '
start state: start
table:
  start:
    x: {R: check}
  check:
    0: {R: havex}
    1: {R: have1}
  havex:
    0: {R: havexx}
    1: {R: havex1}
  havexx:
    0: {R: back0}
    1: {R: havexx1}
  havexx1:
    0: {R: back0}
    1: {R: havexx11}
  havexx11:
    0: {L: back0}
    1: {L: back1}
  havex1:
    0: {R: havex1x}
    1: {R: havex11}
  havex1x:
    0: {R: back0}
    1: {R: havex1x1}
  havex1x1:
    0: {L: back0}
    1: {L: back1}
  havex11:
    0: {R: havex11x}
    1: {R: back1}
  havex11x:
    0: {L: back0}
    1: {L: back1}
  have1:
    0: {R: have1x}
    1: {R: have11}
  have1x:
    0: {R: have1xx}
    1: {R: have1x1}
  have1xx:
    0: {R: back0}
    1: {R: have1xx1}
  have1xx1:
    0: {L: back0}
    1: {L: back1}
  have1x1:
    0: {R: have1x1x}
    1: {R: back1}
  have1x1x:
    0: {L: back0}
    1: {L: back1}
  have11:
    0: {R: have11x}
    1: {R: back1}
  have11x:
    0: {R: have11xx}
    1: {R: back1}
  have11xx:
    0: {L: back0}
    1: {L: back1}
  back1:
    0:  L
    1:  L
    x: {write: 1, L}
  back0:
    0: L
    1: L
    x: {write: 0, L}

[angstigone]

[essepuntato]

Reminder to all: all cells can contain either '0' or '1', no other symbols can be used (despite the fact that the tool online for building Turing Machine allows you to do so).

[AmeliaLamargese]

input: '001011'
blank: '0'
start state: start
table:
  start:
    0: {write: 1, R: Sn}
    1: {write: 1, R: Sn}

  Sn:
    0: {write: 0, R: S0}
    1: {write: 0, R: S1}

  S0:
    0: {write: 0, R: S00}
    1: {write: 0, R: S01}

  S00:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: S001}

  S001:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: S0011}

  S0011:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: END}

  S01:
    0: {write: 0, R: S010}
    1: {write: 0, R: S011}

  S010:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: S0101}

  S0101:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: END}

  S011:
    0: {write: 0, R: S0110}
    1: {write: 0, R: END}

  S0110:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: END}

  S1:
    0: {write: 0, R: S10}
    1: {write: 0, R: S11}

  S10:
    0: {write: 0, R: S100}
    1: {write: 0, R: S101}

  S100:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: S1001}

  S1001:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: END}

  S101:
    0: {write: 0, R: S1010}
    1: {write: 0, R: END}

  S1010:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: END}

  S11:
    0: {write: 0, R: S110}
    1: {write: 0, R: END}

  S110:
    0: {write: 0, R: S1100}
    1: {write: 0, R: END}

  S1100:
    0: {write: 0, L: FAIL}
    1: {write: 0, R: END}

  FAIL:
    0: {write: 0, L: FAIL}
    1: {write: 0, L: END}

  END: