I have a Turing Machine M. Let L be the set of all strings representing the encoding of M that has input alphabet {1,2}, where M accepts infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to determine if L is decidable, semi-decidable (computably enumerable) or undecidable.
Using Rice's Theorem, I believe I can prove that L is not decidable:
P is the property of a language where the language has infinitely many
strings that start with one symbol and finitely many strings that
start with another symbol. P is non-trivial and is a property of
languages of TMs. Therefore, according to Rice's Theorem, M =
{⟨M⟩∣ L includes infinitely many strings that start with 1 and
finitely many strings that start with 2 and Σ = {1,2}} is undecidable.
But I'm struggling to prove whether it's semi-decidable or completely undecidable. This post mentions using an Generalized Rice's Theorem to prove that a language is recursively enumerable (aka semi-decidable) but I'm having trouble understanding their approach.
Can anyone shed some light on this approach and/or if I'm heading down the right path? Many thanks in advance.
Best Answer
Hint: It may be clearer to state that the set of internal states of the Turing machine $T$ is either $\{0,1\}$ for the infinitely (or finitely many strings that it may produce on its tape), especially if the language $\Sigma$ is recursively enumerable (or equivalently, in the range of a partial recursive function $\psi$).
I assume, then, that the language $\Sigma$ is recursively enumerable. We say that $\Sigma$ is decidable if $\Sigma$ lays in the range of a total recursive function $\psi_e(n)$ where $e$ is the code number of the machine $T^e$ that halts on input $n$, and where $n \in \mathbb N$. Intuitively, total recursion holds if $\psi_e$ is defined for every input.
Rice's theorem states that any nontrivial property $P$ of a partial recursive function $\psi_e$ is undecidable (computably unsolvable by $T^e$). We take $P$ to be decidable (either $\psi_e(n)=0$ $\vee$ $\psi_e(n)=1$ if $P$ holds or does not hold, respectively). More directly, let $0'$ be the degree of unsolvability of the problem for deciding if $T^e$ halts on arbitrary input $n$. If the solution set for deciding if $P$ holds is unsolvable, then $P$ is undecidable and the solution set is $0'$.
Therefore, Enumerating the pairs $(n,i)$ if $P$ holds for a string $s_n$ in $\Sigma$ is simply taking $P$ as computable and showing that any $P^i, i \in \mathbb N$ holds or does not hold for a finite (or infinite) $s_n$. Supposing that it does hold, then the solution set it produces should be decidable, as the characteristic $\chi_\Sigma(x) = 0$ if $P(x)$ holds for $x \in \Sigma$ or $\chi_\Sigma(x) = 1$ if $P(x)$ does not hold for $x \in \Sigma$. If this pair is decidable, then the solution set is decidable, since a set is computably enumerable iff its characteristic function is, and not if otherwise. A property of $\psi$ could taken as any property that the sequence of partial functions $\psi_1(n),...,\psi_e(n)$ terminates on input $n$, or if each member of the solution set is a proof that $P(x)$ holds.