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

Improve this question
$\endgroup$
1
  • $\begingroup$ This is often called The Padding Lemma. $\endgroup$
    – John Kemeny
    Commented Jan 6, 2021 at 13:41

5 Answers 5

Reset to default
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.

Improve this answer
$\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
    Commented Jan 1, 2021 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$
    – John Kemeny
    Commented Jan 3, 2021 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
    Commented Jan 4, 2021 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
    Commented Jan 4, 2021 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.

Improve this answer
$\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
    Commented Jan 2, 2021 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
    Commented Jan 2, 2021 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
    Commented Jan 3, 2021 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$
    – John Kemeny
    Commented Jan 4, 2021 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
    Commented Jan 4, 2021 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.

Improve this answer
$\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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.