Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for which adding nondeterminism does not change the computational class.

Is there a class of automata that is not Turing complete, but becomes Turing complete if you add nondeterminism?

  • 1
    $\begingroup$ I'm not sure what you mean that it is in contrast to Turing machines; P vs NP is still open last I checked. $\endgroup$
    – Pål GD
    Feb 1 '19 at 11:31
  • 3
    $\begingroup$ @PålGD The question seems to be about computation theory (i.e., Turing-completeness), not complexity theory. $\endgroup$
    – dkaeae
    Feb 1 '19 at 13:04
  • 2
    $\begingroup$ @PålGD dkaeae is correct. Deterministic turing machines can simulate nondeterministic ones. $\endgroup$
    – PyRulez
    Feb 1 '19 at 18:35
  • $\begingroup$ So when you say computational class, you mean the position in the arithmetical hierarchy? I was not aware of that terminology. $\endgroup$
    – Pål GD
    Feb 2 '19 at 9:49
  • 2
    $\begingroup$ Nitpicking about the phrasing aside, I think the question is clear: Is there a computational model X with class of (non-)deterministically accepted languages (N)X, for which X ⊊ RE but NX = RE? $\endgroup$
    – Raphael
    Feb 2 '19 at 12:01

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.