# Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?

I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions.

My idea was that it is decidable because we have an countably infinite amount of Godel numbers and the number of TMs which fulfill a certain property is also countably infinite. Therefor, we could make a reduction with the Halting-problem and show via this way that it is undecidable.

## 2 Answers

That definitely isn't enough. The set of Turing machines that always halt is countable (being a subset of the countable set of all Turing machines), but very not decidable.

Don't overcomplicate: If you are given a Turing machine, any property of the machine as such (number of states, number of transitions, is it deterministic, ...) that can be checked by a deterministic algorithm is obviously decidable.

I wanted to simply comment this, but given my current reputation, I can't.

I am not sure how broad your definition of properties. But certain properties of a TM may not be decidable. A simple one is to check if an accept state is useful. That is, if the accept state will ever be entered.

To see, we can construct a TM M that when executed ignores its input and simulate the TM M' for the halting problem using a predefined input w'. TM M accepts if M' accepts. So if we can test if the accept state of M is useful then we can solve the halting problem.