6,433 views

2 Answers

6 votes
6 votes

If you only consider that 'Turing machines can always be made to behave like a stack' you can only conclude that they are at least as powerful as pushdown automata.

But in general, yes it is true, Turing machines are more powerful than PDAs. The easiest example would be to show that Turing machines can describe Context Sensitive Languages.

1 votes
1 votes

Turing machine is one of the most powerful machine in this era along with the highest awards in computer science so no machine is more powerful that TM.

Therefore one predescribe chart of impel is given below

TM>LBA>PDA>FSM.

Related questions

1 votes
1 votes
0 answers
1
Akriti sood asked Jan 15, 2017
2,392 views
L={<M | M is a turing machine and it takes less than 481 steps on some input>decidable or R.E??i think it is decidable..just confirm it pls
3 votes
3 votes
1 answer
2
ankitgupta.1729 asked Mar 3, 2018
697 views
Which is more powerful :- 2-way Non-Deterministic Pushdown Machine(NDPDM) or 2-way Deterministic Pushdown Machine(DPDM) ? (or) Do both machine models have the same power ...
11 votes
11 votes
2 answers
3
sourav. asked Sep 9, 2017
4,379 views
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...