Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
