0
$\begingroup$

I came across following points at various sources:

  1. A one-stack Turing machine is really a DPDA.
  2. Turing machine with two stacks can accept any recursively enumerable language (and hence is as expressive as standard TM).
  3. A machine with two counters is sufficient to accept any recursively enumerable language (and hence is as expressive as standard TM).
  4. NTM with tape being used like a stack, leads to PDA.
  5. NTM with only finite part of tape permitted, leads to FA.
  6. NTM with bounded tape (i.e. usable tape size depends on input size), leads to LBA.

Doubts

  1. Are above correct?

  2. 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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.