patternMajor
I'm trying to understand why every language has an infinite number of TMs that accept it
Viewed 0 times
whyinfinitenumbertmsaccepttryingeverylanguagehasunderstand
Problem
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)$} \}$.
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
$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
Solution
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.
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.
Context
StackExchange Computer Science Q#133875, answer score: 30
Revisions (0)
No revisions yet.