2
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\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

Improve this answer
$\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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.