We know that deterministic TMs are countable (enumeration). Does the same hold for NTMs? Are TMs and NTMS equinumerous?

  • 3
    $\begingroup$ What are the differences between the representation of a TM and a representation of a NTM? Can these differences make an enumeration of the NTMs uncountable? $\endgroup$ – Vor Nov 17 '13 at 18:57
  • 1
    $\begingroup$ How do we know that deterministic TMs are countable? Can that technique be used for nondeterministic TMs, too? $\endgroup$ – David Richerby Nov 18 '13 at 17:27
  • 2
    $\begingroup$ Is there a syntax that you can use to describe NTMs? $\endgroup$ – Niel de Beaudrap Nov 18 '13 at 17:28
  • $\begingroup$ Due to popular demand, I deleted my hint, which was: a non-deterministic Turing machine can be described by a string, and so... $\endgroup$ – Yuval Filmus Nov 18 '13 at 17:29
  • $\begingroup$ if every element of a set is fully communicable to someonelse (i.e. you can describe it without ambiguity), then the set of these elements is countable. $\endgroup$ – Denis Nov 19 '13 at 13:50

Why is the class of DTM countable? Because you can code every DTM as a string (the program) over some alphabet. Now you can sort these strings lexicographicaly. Then the function $$f(i\in \mathbb{N}):=\text{the $i$th string in the sorted sequence of DTMs},$$ is a bijection between the natural numbers and the set of DTMs. Hence the set of DTMs is countable.

Now here is the point. You can argue the same for NTMs. Hence the set of DTMs and NTMs are both countable and therefore equinumerous.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.