Examples of Turing Machines: Loops, Halts, and Rewriting

By

Home / Examples of Turing Machines: Loops, Halts, and Rewriting

A Turing Machine that Reads Very Little before Halting

3 Tapes from 1 Turing Machine, image by Mike DeHaan

3 Tapes from 1 Turing Machine: Image by Mike DeHaan

This second finite state machine will stop after reading the first or second symbol. It’s only “function” is to indicate whether the initial symbol is ‘L’, ‘R’ or ‘H.’

  • *State #0 is the halt state.
  • *If State #1 reads ‘L’, then change to state #2L and go left one cell.
  • *If State #1 reads ‘R’, then change to state #2R and go right one cell.
  • *If State #1 reads ‘H’, then change to state #0 and remain.
  • *If State #2L reads ‘L’ then change to state #0 and go left one cell.
  • *If State #2L reads ‘R’ then change to state #0 and go right one cell.
  • *If State #2L reads ‘H’, then change to state #0 and remain.
  • *If State #2R reads ‘L’ then change to state #0 and go left one cell.
  • *If State #2R reads ‘R’ then change to state #0 and go right one cell.
  • *If State #2R reads ‘H’ then change to state #0 and remain.

A Turing Machine that Seeks by Rewriting

This final Turing machine will seek out the ‘H’ symbol in either direction on a two-way-infinite tape. By rewriting the cells, it avoids the infinite loops that could entrap the first example. Since it writes, it is not a finite state automaton.

  • *State #0 is the halt state.
  • *If State #1 reads ‘L’ then change to state #2L and write ‘R’ in this cell.
  • *If State #1 reads ‘R’ then change to state #2R and write ‘L’ in this cell.
  • *If State #1 reads ‘H’ then change to state #0 and remain in this cell.
  • *If State #2L reads ‘R’ then change to state #1 and go left one cell.
  • *If State #2R reads ‘L’ then change to state #1 and go right one cell.

State #1 switches the symbol on the tape, then changes state to travel in the direction it had been instructed to go. After moving, it returns to the starting state in order to read the new cell. If the new instruction on the tape reverses its direction of travel, it will follow all the rewritten cells until it either changes course or halts for ‘H.”

This program has few instructions for states #2L or #2R because it has already written a specific value into the current cell. The programmer knows that #2L will only read an ‘R,’ for example.

Leave a Comment