Handbook of Computer Science(cs) and IT

Turing Machine

The Turing Machine (TM) was invented by Alan Turing in 1936. Turing machines are ultimate model for computer and have output capabilities. The language 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. There is no separate input. Rather, the input is assumed to reside on the tape at the time when the TM starts running.

• 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, if the following two conditions are satisfied.

1. The problem is a decision problem.
2. The Turing machine ‘yes’ for the input that is the Turing machine accepts the language L.

• A Turing machine is said to be decided a problem, if it partially decided the problem and all its computations are halting computations.
• Deterministic algorithms are treated as a special case of non-deterministic ones, so we can conclude that p intersection
• The most famous unsolvable problem in computer theory is whether

P = NP or P ≠ NP

• A language L is called NP-hard language. If L₁ ≤_p L for every L₁ ϵ NP, where the notation ≤_p denotes the polynomial time reducibility relation.
• A language L is said to be NP-complete, if L ϵ NP and L is NP-hard.

 

 

 

 

 

 

 

 

 

Definition of Turing Machine

A Turing Machine (TM) is denoted as 7-tuples (Q, Ʃ, г, δ, q₀, b, F)

Where, Q is a finite not-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 x ┌ ) → (Q x ┌ x {L, R})

i.e. , mapping from the present state a of automata and tape symbol to next state, tape symbol and movements of head in left or right direction along the tape.

q₀ is the initial state and q₀ ϵ Q.

b is the blank and b  ϵ Г.

F is the set of final states and F intersection Q.

	Transition Function of a Turing Machine The transition function (Q x ┌ ) → (Q x ┌ x {L, R}) states that if at 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.

 

 

 

 

 

 

Behaviour of Turing Machine

Depending upon the number of moves in transition, a TM may be deterministic of non-deterministic. If TM has at most one move in a transition, then it is call 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 recognizer. TM recognises all language, 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 Turing 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 mulithead Turing Machine can be viewed as 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 problem 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).

Linear Bound Automata (LBA)

It is possible to limit the tape by restricting the way in which the tape can be used. The way of limiting the tape use is to allow the machine to use only that part of the tape occupied by the input.  This way, more space is available for long input strings than for short strings, generating another class of machines called Linear Bounded Automata (LBA).

Recursive and Recursively Enumerable Language

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  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 language are closed under union, intersection, concatenation and Kleene closure and these language are not closed under complementation.

Key Points

• The complement of a recursive language is recursive.
• The union of two recursive language is recursive.
• 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 language is closed under union.
• If a language is not recursively enumerable, then its complements cannot be recursive.
• If a language L is recursive, then it is recursively enumerable language but vice-versa is not true.

Decidable Problems

A problem is decidable, if there is an algorithm that answer either yes or no or we can say that there is a Turing machine that decides the problem.

Undecidable Problems

A decision problem is undecidable, if a Turing machine may run forever without producing an answer.

Halting Problems

A halting problem is undeciable problem. Alan Turing proved in 1936 that there is no general method or algorithm which can solve the halting problem for all possible inputs.

Computability and complexity

• What can be decided algorithmically is known as
• What resources (time, memory, communication) are needed is known as

Complexity Classes

• P-Class P is also known as PTIME or DTIME complexity. It contains all decision problems which can be solved by a deterministic Turing machine using Polynomial amount of computation time.
• NP-Class NP refers to non-deterministic polynomial time. The complexity class NP, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is know. P is subset of NP.
• NP-Hard A problem A is said to be NP-hard, if for every decision problem L in NP, there is an Oracle machine with an Oracle for A.

An Oracle machine is an abstract machine used to study decision problems. It can be visualised as a Turing machine with a black box, called an Oracle, which is able to decided decision problems in a single  operation.

Polynomial Time Reducibility If L₁ and L₂ are two languages over Ʃ₁ and Ʃ₂ respectively, then  L₁ is said to be polynomial time reducible to L_{2 (}L₁≤L₂), if there is a function  f : Ʃ₁^* → Ʃ₂^*  such that for any string x ϵ Ʃ₁^*, x ϵ L, if and only if f (x) ϵ L₂ and f can be computed in polynomial time.

• NP-Completeness An NP-complete problem is one for which the corresponding language is NP-complete. A language L is NP-complete, if L ϵ NP and L is NP-Hard.

 

Some NP-Complete Problems

Satisfiability problems are given below

• The vertex cover problem.
• The Hamiltonian cycle problem.
• The travelling salesman problem.
• The colorability problem.
• The simple max cut problem.

 

Key Points

• The set of all Turing machines, although infinite is countable.
• The halting problem of Turing machine is undecidable.
• Let M be any Turing machine, then the question of whether or not L (M) s undecidable.
• The post correspondence problem is undecidable.