Skip to main content

Turing Machines

Amu_Ke_Fundye

Turing Machines


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.

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

 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.
  • 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.
Regards 
Amrut Jagdish Gupta
Labels:

Comments

Post a Comment

Popular posts from this blog

Undecidability

Amu_Ke_Fundye Undecidability Decidable Problem If there is a Turing machine that decides the problem, called as Decidable problem. A decision problem that can be solved by an algorithm that halts on all inputs in a finite number of steps. A problem is decidable, if there is an algorithm that can answer either yes or no. A language for which membership can be decided by an algorithm that halts on all inputs in a finite number of steps. Decidable problem is also called as totally decidable problem, algorithmically solvable, recursively solvable. Undecidable Problem A problem that cannot be solved for all cases by any algorithm whatsoever. Equivalent Language cannot be recognized by a Turing machine that halts for all inputs. The following problems are undecidable problems: Halting Problem:  A halting problem is undecidable problem. There is no general method or algorithm which can solve the halting problem for all possible inputs. Emptyness Problem:  Wh
Post a Comment
Read more

ALU and Data Path

Amu_Ke_Fundye ALU and Data Path The CPU can be divided into a data section and a control section. The   data section , which is also called the   datapath. Datapath The registers, the ALU, and the interconnecting bus are collectively referred to as the datapath.  Each bit in datapath is functionally identical.  The datapath is capable of performing certain operations on data items. The  control section  is basically the  control unit ,  which issues control signals to the datapath . Bus : A Bus is a collection of wires or distinct lines meant to carry data, address and control information. Data Bus : it is used for transmission of data. The number of data lines corresponds to the number of bits in a word. Address Bus : it carries the address of the main memory location from where the data can be accessed. Control Bus : it is used to indicate the direction of data transfer and to coordinate the timing of events during the transfer. PC (Pro
Post a Comment
Read more

Sequential Logic Circuits

Amu_Ke_Fundye Sequential Logic Circuits In sequential logic circuit, the output is dependent upon the present inputs as well as the past inputs and outputs. Sequential circuit is of two types. Synchronous Sequential Circuit:  Change in input signals can affect memory elements only upon activation of clock signals. Asynchronous Sequential Circuit:  Change in input signals can affect memory elements at any instant of time. These are faster than synchronous circuit. Flip Flops: It is a one-bit memory cell which stores the 1-bit logical data (logic 0 or logic 1). It is a basic memory element. The most commonly used application of flip flops is in the implementation of a feedback circuit. As a memory relies on the feedback concept, flip flops can be used to design it. In synchronous sequential circuit, Memory elements are clocked flip flops and generally edge triggered. In asynchronous sequential circuit, Memory elements are unclocked flip flops / time delay
2 comments
Read more