# Is the set of non-deterministic Turing machines countable?

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

• 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? – Vor Nov 17 '13 at 18:57
• How do we know that deterministic TMs are countable? Can that technique be used for nondeterministic TMs, too? – David Richerby Nov 18 '13 at 17:27
• Is there a syntax that you can use to describe NTMs? – Niel de Beaudrap Nov 18 '13 at 17:28
• Due to popular demand, I deleted my hint, which was: a non-deterministic Turing machine can be described by a string, and so... – Yuval Filmus Nov 18 '13 at 17:29
• 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. – 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 ith 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.