1
$\begingroup$

Why is this true: “There are countably many Turing Machines”

In the top answer for this question a description of how to enumerate all Turing machines is given.

It all is clear except for one part: how do you know if a string is a valid encoding of a Turing machine? In step 3 the algorithm needs to check if a string is a valid encoding of a Turing machine. How is this done?

$\endgroup$
2
$\begingroup$

A turing machine has a representation as a string. more specifically, you write the transition function. to do this, simply think of it as one big table, having in each row two states a letter, and a head transition (L for left or R for right).

Now, encode every entry of the transition function table, and space between them with 3 zeroes (its like a "magic number" so we would know where entries start and end). every entry will contain two numbers - each number representing one state, another bit for the letter and another bit for the head transition (say 1 would be R and 0 is L).

between the two numbers and the other bits put 2 more zeroes, just so you would be able to distinguish between them.

Now, to enumerate on all of the turing machines, just enumerate on all strings and check if they are in the format described above

$\endgroup$
8
  • $\begingroup$ Can you check if a string is in the format described in polynomial time? Maybe there is another method of encoding TMs that lets you check in poly time if a given string is a TM? $\endgroup$ – DeeDee Jun 10 '20 at 16:25
  • 1
    $\begingroup$ Yes you can check a string for turing machine encoding in polynomial time. In fact, unless you devise some really weird way to format them - the language of the properly formatted strings will be regular, or in very rare cases context-free. They are easy to check. $\endgroup$ – nir shahar Jun 10 '20 at 18:01
  • $\begingroup$ one more question! cs.stackexchange.com/questions/126615/… in this question i ask how you can enumerate over the class P. In this question i ask how to enumerate over all possible TMs. I'm wondering how does my comment above apply to this enumeration of P (or any)? aka, Can you check if a string is a representation of a polynomial turing machine in poly time? Again, maybe there is different method of encoding P machines that lets you check in poly time if a given string is a P machine? $\endgroup$ – DeeDee Jun 18 '20 at 3:07
  • 1
    $\begingroup$ There is a different method for that. You cant check (im pretty sure at least) if a TM is polynomial, and not even if it always halts. Thats why for every TM we will not check if its polynomial but force it to be one by adding a "counter" to it that will forcibly halt the machine if it got past poly time (this would require enumeration of all $x^c$ for every language!) $\endgroup$ – nir shahar Jun 18 '20 at 7:06
  • $\begingroup$ 'Thats why for every TM we will not check if its polynomial but force it to be one by adding a "counter".' Yes, the method is to enumerate over all possible pairs (Polynomial, Turing machine). First, i assume you follow your method to enumerate all TMs. Next i assume you follow a similar method to enumerate all polynomials. Then, you enumerate over all pairs from both lists. $\endgroup$ – DeeDee Jun 18 '20 at 13:53

Your Answer

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