Contents

✓ Turing Machine

Turing Machine is a mechanical machine that manipulates 0’s and 1’s on a tape. It’s simplicity is deceptive, as TM is as expressive as any modern computers. TM is a major device for the development of Computer Science both theoretically and practically.

TM and this course

TM is the foundation of computation on which all computers are modeled after. Despite its primitive construction and theoretical importance, the notion of programming, and how computation can be described through instructions are still vividly obvious once we understand how a TM functions.

Definition of a TM

Tape

A tape is a storage medium consisting of cells that can store symbols and are indexed by 0, 1, 2, etc.

Head

A head is a component that can move from cell to cell, reading or writing the symbols in the cells.

Control Logic

A control logic is a finite state machine that controls the head.

The tape

image.png

Properties of a tape.

  • The TM has an infinitely long tape that is divided into cells. Each cell can been blank, 0, or 1.

  • One or more finitely binary strings can be stored on the tape.

  • The cells are indexed with position 0, 1, 2, 3, …

  • At any time, one position is marked current.

The head

image.png

Properties of a head

  • The head can be positioned at any cell in the tape. The cell with the head is called the current cell.

  • It can read the symbol in the current cell.

  • It can also be instructed to modify the content of the current cell.

Control logic

image.png

  • The control logic is a finite state machine.

  • The control logic is driven by the symbols read by the head.

  • The control logic emits commands to the head.

  • The commands are:

    • No-op

    • Move(left), Move(right), No move

    • Write(blank), Write(0), Write(1)

Example

Execution of TM

Initial condition

  • The TM starts with its control logic in the initial state.

  • The head is set at the left-most position of the tape.

Iteration

  • Read the symbol of the current cell.

  • Look up transition using the read symbol and the current state of the control logic.

  • Execute instructions associated with the transition.

  • Update state of control logic.

Termination

  • Stop the iteration when a halting state is reached.

Pseudo code

Initialization

tape.writeContent(input_string)
control_logic.reset()
head.moveTo(0)

Iteration

while True:
    if state.is_halting():
        break
    read_symbol = head.read_cell()
    
    (write_symbol, movement, next_state) = control_logic.get_transition(state, read_symbol)
    head.write(write_symbol)
    head.move(movement)
    control_logic.goto(next_state)

return tape.content()

Significance of TM

TM can almost be implemented electro-mechanically. The only impractical element of a theoretical TM is its assumption that the tape is infinite.

TM can be used to implement any algorithms. This is known as the Church-Turing thesis.

Note

We will cover the contribution of Alonzo Church in great detail in the section of Lambda Calculus.

Incidentally, Alan Turing completed his PhD under the supervision of Alonzo Church in 1938 at Princeton University.