# I'm trying to understand why every language has an infinite number of TMs that accept it

$$L_{17} = \{ \langle M \rangle \mid \text{M is a TM, and M is the only TM that accepts L(M)} \}$$.

• R. This is the empty set, since every language has an infinite number of TMs that accept it.

As I know number of TMs is $$\aleph_0$$ and number of languages is $$2^{\aleph_0}$$, so how can it be possible that "every language has an infinite number of TMs that accept it"?

source of the solution here

• This is often called The Padding Lemma. Jan 6 at 13:41

The correct version of the claim states that every computable language is accepted by infinitely many Turing machines.

Indeed, if $$L$$ is computable, then there is a Turing machine $$T$$ that accepts it. Let $$T_n$$ be $$T$$ together with $$n$$ unreachable states. Then $$T_n$$ also accepts $$L$$, and the machines $$T_n$$ are all different from one another.

• And the huge majority of languages have exactly zero TMs computing them. So a language has zero TMs accepting it, or a countable infinite number, and nothing in between is possible. Jan 1 at 22:08
• I'm not sure that your claim is what is meant. I think "language" in the question refers to the languages of the form $L(M)$, as is stated in the set comprehension. I'm not sure what exactly is meant by $L(M)$, but I'm not convinced that it is only computable languages; It could also contain recursively enumerable languages. Jan 3 at 16:21
• @gnasher729: I'm wondering about that "countable infinite" - in particular that countable part. Obviously the set Tn in this answer is countable, but does it hold for the entire set of machines which accept L? Jan 4 at 11:58
• There are countably many Turing machines under any reasonable encoding (that is, for any encoding that allows you to describe a Turing machine using a string on a fixed alphabet). Jan 4 at 12:03

Intuitively?

Do you know programming? Can you think of a way of making infinitely many versions of the same program?

Say, adding a function foo that you never call creates a different program, but it still does the same thing.

• Not calling the added functions feels a bit like cheating. But fooN could call fooN-1, which calls fooN-2,.., which calls foo2, which calls foo, which contains the actual program. Jan 2 at 10:43
• @EricDuminil You can add unreachable states to a Turing machine, which is basically the same as adding uncalled functions. Jan 2 at 16:06
• @AndreasT: Sure, it's allowed. I just meant that it feels a bit like adding irrelevant comments to the code. Jan 3 at 23:03
• @EricDuminil there is no such thing as cheating. The statement is that for each Turing machine $M$, there are infinitely other Turing machines that are "equivalent" to $M$. Sure, you can also alter the behavior, like starting with moving $i$ steps right followed by $i$ steps left. But then you can say that that's not changing the behavior, so let's move $i$ steps right, flipping each bit on the tape as we move, and then reversing the operation ... It's just not necessary. Jan 4 at 10:13
• For any $TM, T$, you could create a modified $TM, T'$ which writes a 1 on the first square of the tape, then erases it, then passes control to T. Then both $TMs$ would ultimately compute the same language, but there would be an infinite set of $TMs$ that do so: $T, T', T'', T''', T$ (with a trillion tick marks), $T$(with a trillion and one tick marks), ... etc Jan 4 at 14:55

Note that the quoted sentence should be "R. This is the empty set, since every $$\text{L(M)}$$ has an infinite number of TMs that accept it."

The other answers are correct, and there are other ways to prove that every language that is accepted by some TM, is actually accepted by $$\aleph_0$$ distinct TMs. However, following the last sentence in the question, I believe what may be counterintuitive to you is that there are also $$\aleph_0$$ distinct languages that are accepted by means of TMs. So the question is how come there are $$\aleph_0$$ TMs in total?

Maybe what you're missing is the following claim: the union of countably many countable sets is countable. See here.

Just put a for loop in there. It goes around n times before doing the calculation. There is no limit to the size of n.

The quoted claim is very unfortunate. First because it is written in a clumsy way which makes it wrong as Yuval wrote. Two because it is a huge hammer to smash a tiny nut - all you need is to show that any TM can be modified slightly (usually by making it a tiny bit less efficient) while recognising the same language.