Semidecidability

“Better to keep your mouth shut and be thought a fool
than to open it and remove all doubt.”
—The semidecider motto (and counterproductive for students in a class!)

For some formal language, it can be easier to show a string is a member of the language than to show it is not. This leads to the definition of semidecidable languages, which includes all decidable languages and more:

Language classes

Semidecidability

Definition

A language is semidecidable if it is the language of some TM.

(That is, if it is the set of strings accepted by some Turing Machine.)

The following are all equivalent ways of saying that a language $L$ is semidecidable:

$L$ is the language of some TM $M$ .
There exists a TM $M$ such that $M$ accepts $w$ iff $w\in L$
There exists a TM $M$ such that $M$ accepts every string in $L$ , and does not accept (rejects or runs forever) any string not in $L$ .
There exists a TM $M$ that never lies about whether its input is in $L$ , and if the input is in the language then $M$ can (eventually) figure this out.

Given a formal language $L$ , we can ask whether $L$ is decidable or not. We can also ask whether $L$ is semidecidable or not. Since all decidable languages are semidecidable, there are three possible outcomes:

$L$ is decidable.
$L$ is undecidable but semidecidable.
$L$ is undecidable and not semidecidable.

Language classes

Examples

Example

We previously showed that

A_\mathrm{TM} = \{\ \langle M, w\rangle\ |\ M \mathrm{~a~TM},\ w\in L(M)\ \}

is not decidable, but it is semidecidable.

Proof: We can semidecide the language using a TM that implements the following algorithm:

def semidecide_Atm(M, w):
       return simulate(M, w)

That is, there is a machine (the semidecider) that takes as input the code for a Turing Machine $M$ and a string $w$ , simulates running $M$ on input $w$ (using the techniques of a Universal Turing Machine), and reports the result.

If $\langle M,w\rangle \in A_\mathrm{TM}$ then running $M$ on input $w$ will eventually halt and accept, and so the semidecider will report that.

If $\langle M,w\rangle \not\in A_\mathrm{TM}$ then running $M$ on input $w$ will eventually halt and reject (and the semidecider will report that) or it will run forever (and the semidecider will run forever). In either case, the semidecider will not accept.

semidecide_Atm is not a decider (because it isn’t guaranteed to always return an answer), but it is a valid semidecider because it accepts all and only elements of $A_\mathrm{TM}$ .

Example

The set

\mathit{Accepts}{-}\epsilon = \{\ \langle M, w\rangle\ |\ \epsilon\in L(M)\ \}

of Turing Machines (programs) that halt and except when given an empty string as input (an initially blank tape) is semidecidable. (It’s not decidable, but we won’t prove that until later.)

Proof: We can semidecide the language using a TM that implements the following algorithm:

def semidecide_Accepts_eps(M):
      return simulate(M, "")

That is, there is a machine (the semidecider) that takes as input the code for a Turing Machine $M$ , simulates running $M$ on an empty string, and reports the result.

If $\langle M\rangle \in \mathit{Accepts}{-}\epsilon$ then running $M$ on $\epsilon$ will eventually halt and accept, and so the semidecider will report that.

If $\langle M\rangle \not\in \mathit{Accepts}{-}\epsilon$ then running $M$ on $\epsilon$ will eventually halt and reject (and the semidecider will report that) or it will run forever (and the semidecider will run forever). In either case, the semidecider will not accept.

Thus semidecide_Atm accepts all and only elements of $\mathit{Accepts}{-}\epsilon$ .

Example

The set of Turing Machines

\mathit{NE}_\mathrm{TM} = \{\ \langle M, w\rangle\ |\ \epsilon\in L(M)\ \}

is semidecidable. (It’s not decidable, but we won’t prove that until later.)

Proof: It’s a little less obvious how to figure whether a given TM accepts some string without knowing the string in advance. The problem is that if we simulate the TM on any specific string (e.g., the empty string), the TM might run forever, but had we tried a different string the TM could have halted and accepted immediately.

The trick is to check a string for only a few steps, and then try something else. More specifically, we can enumerate all possible input strings (since they’re countable), and write code that tries a few strings for a few steps each, and then a larger set of strings for a larger number of steps each, and so on. If there is any specific string that can be accepted in any finite number of steps, this strategy will eventually try it for enough steps, see the TM accept, and report the machine as having a nonempty language.

That is, we can semidecide the language using a TM that implements the following algorithm:

def semidecide_NEtm(M):
    n = 0
    while True:
        n += 1
        for w in first_n_strings(n):
            if simulate_n_steps(M, w, n):
              return True

Thus semidecide_NEtm accepts all and only elements of $\mathit{NE}_\mathrm{TM}$ .

Non-Semidecidable Languages

We can show a language is semidecidable by constructing a semidecider. But how can we prove a language is not semidecidable, i.e., that no such semidecider exists?

One way is to use a mapping reduction (as described later), but in some cases we can use the following shortcut:

Theorem

If $L$ is semidecidable and its complement $L^c$ is semidecidable, then $L$ is decidable.

Proof:
Suppose $L$ and $L^c$ are semidecidable.

Then there are Turing Machines $M_1$ and $M_2$ that semidecide $L$ and $L^c$ respectively.

Given an input $w\in\Sigma^*$ , there is a TM that simulates running both $M_1$ and $M_2$ on $w$ in parallel. (It can simulate one step of $M_1$ , then one step of $M_2$ , then another step of $M_1$ , then another step of $M_2$ , and so on.)

Since $M_1$ and $M_2$ are semideciders, if $w\in L$ then $M_1$ will eventually halt and accept $w$ , and if $w\in L^c$ then $M_2$ will eventually halt and accept $w$ .

So we just run the machines in parallel and wait for one to accept, which is guaranteed to happen in a finite amoutn of time. If $M_1$ accepts, then we know $w\in L$ , and if $M_2$ accepts, then we know $w\in L^c$ so $w\not\in L$ .

Thus $L$ is decidable.

Corollary

If $L$ is semidecidable but not decidable, then $L^c$ is not even semidecidable.

Proof: Suppose $L$ is semidecidable but not decidable.

If $L^c$ were semidecidable, by the above theorem $L$ would be decidable, but it’s not.

So $L^c$ can’t be semidecidable.

Example

Since we know that

A_\mathrm{TM} = \{\ \langle M, w\rangle\ |\ w\in L(M)\ \}

is semidecidable but not decidable, its complement

\lnot A_\mathrm{TM} = \{\ \langle M, w\rangle\ |\ w\not\in L(M)\ \}

is not even semidecidable.