Turing Machine

The languages accepted by Turing machine are said to be recursively enumerable. A Turing Machine (TM) is a device with a finite amount of read only hard memory (states) and an unbounded amount of read/write tape memory.

  • Recursive languages are closed under complementation, union, intersection, concatenation and Kleene closure.
  • A Turing machine is said to be partially decide a problem, if the following two conditions are satisfied.
    1. The problem is a decision problem.
    2. The Turing machine accepts as given input if and only if the problem has an answer ‘yes’ for the input that is the Turing machine accepts the language L.
  • A Turing machine is said to be decide a problem, if it partially decides the problem and all its computations are halting computations.

 

A language L is Turing-recognisable if there is a Turing machine M such that L=L(M).

A language L is Turing-decidable if there is a Turing machine M such that M decides L.

Turing-decidable language is also Turing-recognisable, but Turing-recognisable may not be Turing-decidable.

A language is recursively enumerable iff it is Turing-enumerable.

 

 

Universal Turing Machine (UTM)

  • A UTM is a specified Turing machine that can simulate the behaviour of any TM.
  • A UTM is capable of running any algorithm.

 

For simulating even a simple behaviour, a Universal Turing Machine must have a large number of states. If we modify our basic model by increasing the number of read/write heads, the number of dimensions of input tape and adding a special purpose memory, then we can design a Universal Turing Machine. 

Definition of Turing Machine

A Turing Machine (TM) is defined as 7-tuples.

TM = (Q, Σ, Γ, δ, q0, b, F), 

where, Q is a finite non-empty set of states, Σ is a non-empty set of input symbols (alphabets) which is a subset of Γ and b ∈ Σ, Γ is a finite non-empty set of tape symbols, δ is the transition function which maps (Q × Γ) to (Q × Γ × {L, R}), q0 is the initial state and q0 ∈ Q, b is the blank and b ∈ Γ, F is the set of final states and F ⊆ Q.

 

Transition Function of a Turing Machine

The transition function Q × Γ → Q × Γ × {L, R} states that if a Turing machine is in some state (from set Q), by taking a tape symbol (from set Γ), it goes to some next state (from set ï) by overwriting (replacing) the current symbol by another or same symbol and the read/write head moves one cell either left (L) or right (R) along the tape.

1

 

  2

 

3. Construct a TM that accepts the language A = {0(2^n) | n>=0}

 

tm1

Behaviour of Turing Machine

Depending upon the number of moves in transition, a TM may be deterministic or non-deterministic. If TM has at most one move in a transition, then it is called Deterministic TM (DTM), if one or more than one move, then Non-deterministic TM (NTM or NDTM).

  • A non-deterministic TM is equivalent to a deterministic TM.
  • Some single tape TM simulates every 2 PDA (a PDA with two stacks).
  • The read only TM may be considered as a Finite Automata (FA) with additional property of being able to move its head in both directions (left and right).

 

Language Recognition by Turing Machine

TM can be used as a language recogniser. TM recognises all languages, regular language, CFL, CSL, Type-0.

 

There are several ways an input string might fail to be accepted by a Turing machine

  • It can lead to some non-halting configuration from which the Turing machine cannot move.
  • At some point in the processing of the string, the tape head in scanning the first cell and the next move specifies moving the head left off the end of the tape.
  • In either of these cases, we say that the Turing machine crashes

 

Variation of TM with other Automata

  • Multitape Turing Machine A Turing machine with several tapes is said to be a multitape Turning machine. In a multitape Turing machine, each tape is controlled by its own independent read/write head.
  • Turing machine with multiple tape is no more powerful that one tape Turing machine.
  • Multi-dimensional Turing Machine A Turing machine is said to be multi-dimensional Turing machine, if its tape can be viewed as extending infinitely in more than one dimension.
  • Multihead Turing Machine A multihead Turing machine can be viewed as a Turing machine with a single tape and a single finite state control but with multiple independent read/write heads.
  • In one move, the read/write heads may take move independently left, right or remain stationary
  • Offline Turing Machine An offline Turing machine is a multitape Turing machine whose input tape is read only (writing is not allowed). An offline Turing machine can simulate any Turing machine A by using one more tape than Turing machine A. The reason of using an extra tape is that the offline Turing machine makes a copy of its own input into the extra tape and it then simulate Turing machine A as if the extra tape were A’s input.

Halting Problem of Turing Machine: A class of problems with two output (true/false) is called solvable (or decidable) problem, if there exists some definite algorithm which always halts (also called terminates), else the class of problem is called unsolvable (or undecidable.

Recursive and Recursively Enumerable Languages

A language L is said to be recursively enumerable, if there exists a Turing machine that accepts it.

A language is recursive if and only if there exists a membership algorithm for it. Therefore, a language L on Σ is said to be recursive, if there exists a Turing machine that accepts the language L and ‘it halts on every ω∈Σ+.

Recursively enumerable languages are closed under union, intersection, concatenation and Kleene closure and these languages are not closed under complementation.

  • The complement of a recursive language is recursive.
  • The union of two recursive languages is recursive.
  • The union of two recursiv enumerable languages is recursive enumerable.
  • Intersection of two recursive languages isrecursive.
  • There are some recursively enumerable languages which are not recursive.
  • If L is recursive then, L’ is also recursive and consequently both languages are recursively enumerable.
  • A language is recursive iff both it and its complement are recursively enumerable.
  • A language L is lexicographically Turing-enumerable iff there is a Turing machine that lexicographically enumerates it.
  • A language is recursive iff it is lexicographically Turing-enumerable.
  • Every context sensitive language is recursive.
  • The family of recursively enumerable languages is closed under union.
  • If a language is not recursively enumerable, then its complements cannot be recursive.
  • If a languages L is recursive, then it is recursively enumerable language but vice-versa is not true.

An infinite set is countable if and only if there is a one-to-one correspondence between its elements and the natural numbers. Otherwise it is said to be uncountable.

  • If Σ is a finite set then Σ ∗ is countable.
  • For every alphabet Σ there is a language L ⊆ Σ ∗ that is not recursively enumerable.
  • There exists a language L that is recursively enumerable but not decidable.
  • The halting problem is the problem of deciding whether a given Turing machine halts when presented with a given input. The halting problem is not decidable.