6
$\begingroup$

I found the following answer:

$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

$\endgroup$
1
  • $\begingroup$ This is often called The Padding Lemma. $\endgroup$ – Pål GD Jan 6 at 13:41
30
$\begingroup$

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.

$\endgroup$
4
  • 12
    $\begingroup$ 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. $\endgroup$ – gnasher729 Jan 1 at 22:08
  • $\begingroup$ 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. $\endgroup$ – Pål GD Jan 3 at 16:21
  • $\begingroup$ @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? $\endgroup$ – MSalters Jan 4 at 11:58
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Jan 4 at 12:03
19
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Duminil Jan 2 at 10:43
  • 9
    $\begingroup$ @EricDuminil You can add unreachable states to a Turing machine, which is basically the same as adding uncalled functions. $\endgroup$ – Andreas T Jan 2 at 16:06
  • $\begingroup$ @AndreasT: Sure, it's allowed. I just meant that it feels a bit like adding irrelevant comments to the code. $\endgroup$ – Eric Duminil Jan 3 at 23:03
  • 1
    $\begingroup$ @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. $\endgroup$ – Pål GD Jan 4 at 10:13
  • $\begingroup$ 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 $\endgroup$ – Hank Igoe Jan 4 at 14:55
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\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.