I came across following points at various sources:
- A one-stack Turing machine is really a DPDA.
- Turing machine with two stacks can accept any recursively enumerable language (and hence is as expressive as standard TM).
- A machine with two counters is sufficient to accept any recursively enumerable language (and hence is as expressive as standard TM).
- NTM with tape being used like a stack, leads to PDA.
- NTM with only finite part of tape permitted, leads to FA.
- NTM with bounded tape (i.e. usable tape size depends on input size), leads to LBA.
Are above correct?
I was wondering what else can be there? I mean how each of finite automata, pushdown automata and turing machine (and their deterministic and non deterministic variants) can emulate other?