“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:
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:
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:
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 accept 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\ |\ L(M) \neq \emptyset \} \] 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}\).
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.
Previous: 6.18 Decidability and Undecidability
Next: 6.20 Reductions