TOC-Turing Machine

  • Turing Machines are general purpose, meaning that they can take the encoding of a computation model and simulate the behavior.
  • Turing Machines are more powerful than modern computers. Whatever we can do on a computer, Turing Machines can do the same.
  • Turing Machines have the same computational power as - calculus. (By Alonzo Church) and recursion functions (by Kurt Godel).
  • Even Turing Machines are not ultimate. Those unsolvable problems are beyond the limit of computation.

Definition

A Turing Machine is a 7-tuple:
where are finite sets, and:

  1. is the set of states,
  2. is the input alphabet (),
  3. is the tape alphabet ( and ),
  4. is the transition function,
  5. is the start state,
  6. is the accept state, and
  7. is the reject state, where .

A Turing Machine can be described as

  • a control unit, which a state machine;
  • an infinite tap;
  • the control unit can read and write on the tap;
  • the control unit can move left and right;
  • the control unit has special states for rejecting and accepting take immediate effect.

Example

Let and a Turing Machine be described as follows to recognize . operates on input string as follows:

  1. Read the input onto the tape.

  2. Ensure that has exactly one , otherwise reject.

  3. Zig-zag across the tape to the corresponding positions on either side of to check whether these positions contain the same symbol.

    • Cross out the symbols if they are the same; otherwise, reject.

  4. When all symbols to the left of are crossed out, check the symbols to the right of .

    • If all are crossed out, accept; otherwise, reject.

is not context free.

Problem:
Input: Given a string in
Question: Is ?

Algorithm:

  1. load on to memory
  2. Check if has only one #, reject if no
  3. Repeat until no unmarked symbol
    • Find the first unmarked symbol in first half
    • Go right, exceed find the first unmarked symbol in second half
    • mark s'
    • reject if
    • go left exceed find the first unmarked symbol in first half
  4. accept if no more in second half.
Formal Definition

The above example shows the basic features of a Turing Machine.

  • (Preprocessing) Read the input (over an alphabet ) onto the tape and move the head to the first symbol in the input.

  • Note: The preprocessing is trivial, tedious, and required by every Turing Machine (TM). Thus, this part of the TM is always omitted.

  • To cross out symbols, a set of tape symbols has to be defined.

    • also contains a blank symbol to show that a tape cell is empty.
    • .

  • is the start state.

  • is the accept state.

  • is the reject state, where .

  • The state machine has a transition function:
    of the input:

    • A current state in , and
    • A tape symbol in in the cell currently pointed to by the state machine.

  • And of the output:

    • The next state in ,
    • The new tape symbol in replacing the symbol in the current cell, and
    • Either or , the direction that the state machine is moving.

Computation on TMs

Accept
A TM accepts a string if it halts on the input at an accepting state.

Reject
A TM rejects a string if it halts on the input at a reject state.

If the transition function is only a partial function (some elements in the domain is undefined),

A TM rejects a string if

  • it halts on the input at a reject state, or
  • it has no where to move in the middle of the process.

Using a partial transition function can omit the reject states.
To make a partial function be total, we just artificially add those undefined transitions to a reject state.

Language

The language for TM are of two types.

A language is recursive or Turing-decidable if there is a TM such that

  • , accepts ; and
  • , rejects .

We say decides .

A language is recursively enumerable (or Turing-recognizable) if there is a TM such that

  • , accepts ; and
  • , rejects or loops forever.

We say recognizes .

Side Effect

When a TM halts on an input,

  • the current state "accept" or "reject" is the output;
  • the content remains on its tape is the side effect.

A TM has a side effect if users need to read tape content to get the desired output. (Using only states of the TM is insufficient to express the output.)

If a TM has no side effect and is only used for checking its output, it is pure; otherwise, it is impure.

Table Of Contents
TOC-Turing Machine
Definition
Example
Computation on TMs
Language
Side Effect