CODEWITHSUNDEEP
turing-machinesdecidable
3932695
3932695

Reputation: 87

Is this language decidable, recognizable, or unrecognizable?

The language L that consists of all Turing Machine descriptions M, for which the language accepted by M is finite.

I said L is a decidable language because I can just run M on a function D(M) that returns false if there exists a loop somewhere between start and accept state of M, and returns true otherwise.

I have a feeling that I am wrong because I am underestimating the difficulty of detecting an infinite loop.

Assistance is appreciated, thank you in advance.

Upvotes: 2

Views: 1128

Answers (1)

Patrick87
Patrick87

Reputation: 28302

If you could decide this language, you could decide the halting problem.

Suppose M is a machine and x is its input. The halting problem is to say whether or not M halts on x. Consider a machine N that clears the tape and writes x in place of whatever input was there before. Now consider the machine obtained by running N and then running M. This machine accepts all inputs if M accepts x, and no inputs otherwise. If you could say for any machine whether the language accepted is finite, you'd be able to say whether M halts on x or not. But that was the halting problem.

Upvotes: 1

Related Questions