TOC-Universal Turing Machine

Describe a TM

A TM can be defined as a 7-tuple.

  • by pseudo-code
  • in a natural language

The input of a TM is a string.
But the input of an algorithm can be any well-defined mathematical object.
If TM and algorithm are equivalent, we need to describe the input of an algorithm as a string.

The description is an encoding of the input.

Suppose the input is , then the encoding is denoted as , which is a string over a specific alphabet.

We also assume that each is programmed to decode and fully understand the meaning carried by .

M can be designed on high-level.
M = "On the input , where is a DFA and is a string:

    1. Simulate on w.
    1. If accepts , accepts ; otherwise rejects ."

The simulation uses a multi-head 2-D tape TM .

Suppose has n states and m symbols in . The encoding of , is as follows.

  • puts on the "first" row if its tape.
  • The "second" (below the first) row contains a sequence of symbols which represents the final states.
  • From the third row, M has a 2 dimensional area of size to represent as a transition table, s.t.
    • the first row and the first column contain only # to show the borders of the transition table;
    • the second row enumerates all symbols in ; and
    • the second column enumerates all states in and the first state is the start state.

M has 5 computation heads which do the following operations.

  • iterates on the first column in the transition table and points to the current state of .
  • iterates on the first row in the transition table and searches the next input symbol from the row.
  • follows and and checks the entry in the transition table to show the next state.
  • iterates on the row for final states to verify whether enters a final state when all inputs are consumed.
  • reads the input for from left to right.

Initially:

  • points to the initial state in the transition table.
  • is at the same position as .
  • is at the cell left to the first symbol (on the second row and the second column of the transition table).
  • is at the leftmost final state on its row.
  • is pointing to the first symbol in the input.

With the encoding of and the configuration of computation heads, simulates on input as follows:

  1. If the cell pointed by has a symbol , which is not empty.
  2. searches on its row (moving right).
  3. moves right simultaneously and stops when stops.
    ( moves right and stops on the same column as .)
  4. Move (up and down) to the state pointed by .
  5. Move to the position of (using the border).
  6. Initialize the position of (using the border).
  7. Move right by one cell.
  8. Repeat all the above until points to empty.
  9. Use to search the state pointed by in final states.
    Accept if found; reject otherwise.

Universal TM

A Universal Turing Machine on the input is a special Turing machine in which:

  • is the encoding Turing machine ,
  • is the encoding of an input of , and
  • simulates on the input .

The definition of a universal Turing machine captures the true meaning of Church-Turing Thesis.

TM is a universal computation model, which is the foundation of computers.

Table Of Contents
TOC-Universal Turing Machine
Describe a TM
Universal TM