# Given a Turing machine M, is there a TM that computes the number of states M has?

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

• 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... Jun 21, 2018 at 16:20
• @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? Jun 21, 2018 at 16:28
• 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. Jun 21, 2018 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).