Deciding set of all Turing machine codes of TMs accepting languages of cardinality $\leq 10$.

Question

Problem:

I need to show that the following language is decidable and if not, if $S$ or $\overline{S}$ is partialy decidable language.

$S=\{w_e\;|\;|L(M_e)|\leq 10\}$

That is set of all Turing machine codes of TMs accepting languages of cardinality $\leq 10$.

So far:

I already know that in order to finish this exercise, I need to show that S is not recursive and I can show it by showing $S$ or $\overline{S}$ is not semidecidable. (Post theorem)

However, I am not sure how to start, since i only intuitively know that we cannot "count" the size of language by looking on TM code.

How should I formalize this?

Answer 1

You can reduce the Halting Problem to this problem. For each integer $e$ let $M_e$ be the $e$-th Turing machine, and let $\varphi_e$ be the partial function it computes. We write $\varphi_e(x)\downarrow$ iff $M_e$ halts on input $x$ ($M_e$ accepts $x$), otherwise we write $\varphi_e(x)\uparrow$.

Let $K = \{e\mid \varphi_e(e)\downarrow\}$, so $K$ is the set of all (codes $e$ of) Turing machines which halt on the code for themselves. $K$ is semidecidable, and not decidable.

Let $S = \{e\mid \varphi_i(x)\downarrow \text{ for at most $10$ $x$'s}\}$.

$S$ is not decidable

Define a reduction $f\colon K\to S$ as follows: $f(e)$ is the code for a Turing machine which on input x behaves in this way:

• If $x < e$ or $x+10 \le x$, loop forever;
• if $x = e+i$ for $1\le i \le 9$, halt (accept x);
• otherwise (x=e), run $M_e$ on $e$, halting iff $M_e$ halts on $e$.

Clearly,

• $\varphi_{f(e)}(x)\uparrow$ for $x < e$ or $x+10 \le x$,
• $\varphi_{f(e)}(e+i)\downarrow$ for $1\le i \le 9$, and
• $\varphi_{f(e)}(e)\downarrow \iff \varphi_{e}(e)\downarrow \iff e\in K$.

Thus if $S$ were decidable, then $K$ would be decidable.

$\overline{S}$ is semi-decidable

$\overline{S}$ is the set of all codes for TMs which halt on 11 or more inputs. There is a TM which on input $e$ computes the following program:

# input: e
s = 11
while True:
    count = 0
    for x = 1 to s:
        run M_e on input x for (at most) s steps;
        if M_e halted on x in s steps: 
            count = count + 1
    if count >= 11:
       return True    # halt, accept e
    # otherwise, bump s and loop again
    s = s + 1

If $M_e$ accepts $11$ or more $x$'s, let the first $11$ be $x_0 < x_1 < \dotsc < x_{10}$. Let $s_i$ be the number of steps $M_e$ takes to halt on input $x_i$, and let $s = \max(x_{10}, s_0, \dotsc, s_{10})$. Then when the program variable s equals $s$, count will reach $11$ and the above algorithm will halt, accepting $e$. Conversely, if the above algorithm halts/returns True on input e, then clearly $M_e$ accepts at least $11$ inputs.