HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Given a Turing Machine M, are there infinitely many Turing machines that recognize L(M)?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
infinitelyarerecognizethatmanymachineturingmachinestheregiven

Problem

I want to show this problem is decidable by describing a TM that answers the question.

I originally thought this was quite simple, and that the answer would just be a TM that outputs "yes" for any valid input of a TM M. My reasoning was that given any TM M, we can just add a new unreachable state to it and the new machine M' will still recognize the same language as M.

However, a Turing machine can only have a finite set of states so now I'm unsure if this reasoning is correct in order to produce infinitely many Turing machines and I'm unsure where to go from here.

Any help would be much appreciated.

Solution

Your attempt is fine. Yes, a Turing machine can only have a finite number of states, but you can add $i$ unreachable states for any natural number $i$ and there are infinitely many natural numbers, even though each one of them is finite.

Context

StackExchange Computer Science Q#84157, answer score: 5

Revisions (0)

No revisions yet.