Modification of Turing Machine

 

Modification of Turing Machine

Simple Turing machine has recognization and computability capability.Simple turing machine use read and write tape instead of read only tape.finite control that can move left and right both direction so that simple turing machine perform all computation(addition,subtraction,multiplication, etc).If  modify the turing machine the power of turing machine whether altered or not after modifications.

Modification in simple turing machine

• Two stack Pushdown automata.
• Read only Turing machine and two way finite automaton.
• Multi tape turing machine.

Two stack Pushdown automata

Push down automata has only single stack storage and can recognize only the context free context free languages.Push down automata with two stack is known as 2PDA. Instruction set of 2PDA is same as PDA only difference is is the operation of the second stack.Power of 2PDA is more than PDA because PDA recognize only context free language but  2PDA  can also recognize non-context free language like type 1,type 0.

Example

Consider the language L=aⁿbⁿcⁿ  

That is non context free language . How 2PDA recognize this language.

Solution

That is non context free language that is not recognize by PDA . Using 2PDA can recognize this language follow these steps:

• Reads all the a from the beginning of the input string and write on the first stack.
• Read all the b from the input string and for each b , read symbol a from the first stack and write X on the second stack.
• Read all c from the input string and match with X from the second stack.

So its prove 2PDA is more powerful than PDA.

But single tape turing machine simulate a 2PDA.

if divide the tape of turing machine into three regions separated by some symbol.

The first region represent the 2PDA input tape the second region represent the first stack and the third region represent the second stack of 2PDA .The read instruction of the 2PDA is simulated by the instruction of turing machine that read the symbol at the corresponding cell from the tape and replace the read symbol by #.

Its prove that simple Turing machine can do whatever a 2PDA can do. 

TM=2PDA

Read only Turing machine and two way automaton

Turing machine use read and write tape .If  restrict a turing machine to read only.That turing machine cannot write any output and therefore cannot compute any function that require writing .But that turing machine can recognize language.The read only turing machine may consider similar as finite automaton that has additional property of being able to move its head in both direction which is known as two way finite automata. The additional thing which has infinite tape.

So that prove

Two way  finite automata=Read only Turing machine

Two way finite automata recognize the regular language and have equivalent language power what read only turing machine have.

Multitape Turing machine

In multitape Turing machine has multiple tape and it can have a separate tape head for each of its multiple tape.The machine read the symbol under all the tape head simultaneously.Head movement on each tape cells independently either one cell right or left and some time stationary also.

Multitape turing machine equivalent to a single tape turing machine.

• Head point to the a in first tape.
• Head point to a in second tape but shift to the until b occur so now head point to b in second tape.

• Now read a from first tape and convert into X and read b from second tape and convert int Y.

So multitape turing machine recognize   L=aⁿbⁿ

Single tape turing machine also recognize    L=aⁿbⁿ

 

 

• Head point to the a  in single tape turing machine read a from tape and convert into X and move right until get b and convert b into Y.
• Repeat until X and Y left in the tape.

So single tape turing machine also recognize  L=aⁿbⁿ

So power of TM=MTM.