Turing Machine represents a model of computational machine with equivalent computational power with respect to any computer.
Computational power of a device is class of problems which can be solved by it.
It was realized later that a Finite Automata can recognize basic patterns in the given input called as Regular Expression.
A FA with one extra stack has more computational power than a FA with no stack. Also called as PDA.
A PDA with one more extra stack has even more computational power than a PDA can solve more general class of problems. also called as TM.
Interestingly, TM has most computational power and adding any thing else to it only increases the speed which with the calculation can be done and not the computational power.
Hence, various Automata have been stated with minor variations to TM which are even equally powerful.
1. Turing machine with Stay Option:
2. Turing machine with multiple tracks.
3. TM with semi infinite tape.
4. Offline Turing Machine.
5. Multi dimensional TM
6. Non Deterministic TM
7. Universal TM
But there are various ways to reduce its power for example.
1. A pushdown automaton can be regarded as a Non Deterministic TM with a tape that is restricted to being used as a stack.
2. Also a finite automata is a turing machine where only a finite part of the tape can be used as work space.
3. Another Interesting automata is Linearly bounded Automata in which you strict the tape length to be exactly same as input length.
It is still not known whether Deterministic and Non deterministic LBA's are equivalent or not..
But LBA are less powerful than TM but more powerful than a PDA.
Computational power of a device is class of problems which can be solved by it.
It was realized later that a Finite Automata can recognize basic patterns in the given input called as Regular Expression.
A FA with one extra stack has more computational power than a FA with no stack. Also called as PDA.
A PDA with one more extra stack has even more computational power than a PDA can solve more general class of problems. also called as TM.
Interestingly, TM has most computational power and adding any thing else to it only increases the speed which with the calculation can be done and not the computational power.
Hence, various Automata have been stated with minor variations to TM which are even equally powerful.
1. Turing machine with Stay Option:
2. Turing machine with multiple tracks.
3. TM with semi infinite tape.
4. Offline Turing Machine.
5. Multi dimensional TM
6. Non Deterministic TM
7. Universal TM
But there are various ways to reduce its power for example.
1. A pushdown automaton can be regarded as a Non Deterministic TM with a tape that is restricted to being used as a stack.
2. Also a finite automata is a turing machine where only a finite part of the tape can be used as work space.
3. Another Interesting automata is Linearly bounded Automata in which you strict the tape length to be exactly same as input length.
It is still not known whether Deterministic and Non deterministic LBA's are equivalent or not..
But LBA are less powerful than TM but more powerful than a PDA.
From where can i get more detailed explanation about PDA and Turing machine?
ReplyDelete