I've seen it used but I can't think of a way to construct such TM. Would appreciate any help!

  • 3
    $\begingroup$ I am a bit confused. Isn't the set of states given in the definition of a TM? The problem is essentially counting the number of elements in a set then... $\endgroup$ – xuq01 Jun 21 '18 at 16:20
  • 1
    $\begingroup$ @xuq01 by definition of a TM you mean the encoded input of a TM? I'm a bit confused about universal TM's and how you use the input of an encoded TM. So given the encoded definition of a TM I can compute its number of states? By that logic also the alphabet, etc? $\endgroup$ – Dina Benyamin Jun 21 '18 at 16:28
  • $\begingroup$ Yes. A TM is a 7-tuple, and one of the elements is the set of states. A correct encoding of a TM should encode all 7 elements. So, if you have a correct encoding of a TM it should be trivial to get the set of states, the alphabet, etc. $\endgroup$ – xuq01 Jun 21 '18 at 17:16

I think you are a bit confused about TMs. A Turing machine, by canonical definition (as found in textbooks like [Sipser 1996], [Papadimitriou 1982] and [Hopcroft and Ullman 1979], as well as on Wikipedia), is a 7-tuple, one of which is $Q$, the set of states. So, the set of states of a Turing machine is not computed; it is part of the definition of a TM.

In case of a universal TM, the input to the TM is the encoding of another TM (as well as its input). If you are familiar with functional programming, this is similar to a meta-circular evaluator (it is also similar to the eval function in some programming languages).

So, an encoding of a TM should encode all 7 elements that comprise the TM. Which means that a correct encoding of a TM must encode an enumeration of the set $Q$. Now, you can construct another TM that operates on the encoding of TMs (again, if you have done FP, it is similar to higher-order functions in FP).

If you know the encoding used, it should be trivial to retrieve the set of states of the input TM. You do need to count the number of elements in that set, but that should be Turing computable (because the set of states has to be finite). Now you have a TM that computes the number of state that another TM has.


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.