0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.