3Computability theory
III Logic
3.2 Decidable and semi-decidable sets
So we’ve managed to come up with a notion of computability of a function. From
now on, we will assume anything that is “intuitively computable” is actually
computable.
We now want to try to talk about “computable subsets” of
N
. There are two
possible things we might be interested in.
Definition
(Decidable set)
.
A subset
X ⊆ N
is decidable if there is a total
computable function N → N such that
f(n) =
(
1 n ∈ X
0 n 6∈ X
.
This is a rather strong notion. We can always tell, in finite time, whether
an element is in
X
. Often, a weaker notion is desired, namely semi-decidability.
Informally, a subset
X ⊆ N
is semi-decidable if upon given some
n ∈ X
, if
n ∈ X
,
then we can learn this in finite time. If
n 6∈ X
, we might never figure this is the
case.
There are several ways to define semi-decidable sets properly.
Definition
(Semi-decidable set)
.
We say a subset
X ⊆ N
is semi-decidable if it
satisfies one of the following equivalent definitions:
(i) X is the image of some partial computable function f : N → N.
(ii) X is the image of some total computable function f : N → N.
(iii) There is some partial computable function f : N → N such that
X = {n ∈ N : f(n) ↓}
(iv) The function χ
X
: N → {0} given by
χ
X
=
(
0 n ∈ X
↑ n 6∈ X
is computable.
There are obvious generalizations of these definitions to subsets of
N
k
for any
k
. It is an easy, and also important, exercise to prove that these are equivalent.
We can prove another equivalent characterization of semi-decidable sets.
Proposition.
A set
X ⊆ N
k
is semi-decidable iff it is a projection of a decidable
subset of N
k+1
.
Proof.
(
⇐
) Let
Y ⊆ N
k+1
be such that
proj
k
Y
=
X
, where
proj
k
here denotes
the projection to the first
k
factors. Since
Y
is decidable, there is a computable
function
f
:
N → N
k+1
such that
im f
=
Y
. Then
im
(
proj
k
◦ f
) =
X
. So
X
is
the image of a computable function.
(
⇒
) Suppose
X
is semi-decidable. So
X
=
dom
(
{m}
) for some
m ∈ N
, i.e.
X = {n : {m}(n) ↓}. Then we can pick
Y = {(x, t) | {m}(x) halts in t steps}.
A crucial example of a semi-decidable set is the halting set.
Definition (Halting set). The halting set is
{hp, ii : {p}(i) ↓} ⊆ N
2
.
Some people prefer to define it as
{m : {m}(m) ↓} ⊆ N
instead.
These two definitions are “the same” in the sense that if we are given some
magic “oracle” that determines membership of one of these sets, then we can
use it to build a program that determines the other. (Exercise)
Theorem (Turing). The halting set is semi-decidable but not decidable.
The proof is just some version of Liar’s paradox.
Proof.
Suppose not, and
M
is a machine with two inputs such that for all
p, i
,
we have
M(p, i) =
(
yes {p}(i) ↓
no {p}(i) ↑
.
If there were such a machine, then we could do some “wrapping” — if the output
is “yes”, we intercept this, and pretend we are still running. If the output is
“no”, then we halt. Call this
M
0
. From this, we construct
M
00
(
n
) =
M
0
(
n, n
).
Suppose this machine is coded by m.
Now does
{m}
(
m
) halt? Suppose it does. Then
M
(
m, m
) =
yes
, and hence
M
0
(
m, m
) does not halt. This means
m
(
m
) doesn’t halt, which is a contradiction.
Conversely, if
m
(
m
) does not halt, then
M
0
(
m, m
) says
no
. Thus,
m
(
m
)
halts. This is again a contradiction!
So M cannot exist.
So the problem of deciding whether a program halts is not decidable. In fact,
we can prove something much stronger — any non-trivial question you can ask
about the behaviour of the function represented by a program is undecidable.
To prove this, we need to go through a few equally remarkable theorems.
Theorem
(
smn
theorem)
.
There is a total computable function
s
of two vari-
ables such that for all e, we have
{e}(b, a) = {s(e, b)}(a).
Similarly, we can find such an s for any tuples b and a.
This is called the
smn
theorem because the function is called
s
, and
m
and
n usually refers to the length of the tuples b and a.
Computer scientists call this process “currying”.
Proof. We can certainly write a program that does this.
Theorem
(Fixed point theorem)
.
Let
h
:
N → N
be total computable. Then
there is an n ∈ N such that {n} = {h(n)} (as functions).
Proof. Consider the map
he, xi 7→ {h(s(e, e))}(x).
This is clearly computable, and is computed by a machine numbered
a
, say. We
then pick n = s(a, a). Then we have
{n}(x) = {s(a, a)}(x) = {a}(a, x) = {h(s(a, a))}(x) = {h(n)}(x).
This is a piece of black magic. When we do lambda calculus later, we will see
that this is an example of the
Y
combinator, which is what is used to produce
fixed points in general (and is also black magic).
Theorem
(Rice’s theorem)
.
Let
A
be a non-empty proper subset of the set of
all computable functions N → N. Then {n : {n} ∈ A} is not decidable.
This says it is impossible to decide what a program does based on what its
code is.
Proof.
We fix an
A
. Suppose not. We let
χ
be the (total) characteristic function
of
{n
:
{n} ∈ A}
. By assumption,
χ
is computable. We find naturals
a, b
such
that
{a} ∈ A
and
{b} 6∈ A
. Then by the hypothesis, the following is computable:
g(n) =
(
b {n} ∈ A
a otherwise
.
The key point is that this is the wrong way round. We return something in
A
if the graph of
{n}
is not in
A
. Now by the fixed point theorem, there is some
n ∈ N such that
{n} = {g(n)}.
We now ask ourselves — do we have
{n} ∈ A
? If so, then we also have
{g
(
n
)
} ∈ A
.
But these separately imply
g
(
n
) =
b
and
g
(
g
(
n
)) =
b
respectively. This implies
g(b) = b, which is not possible.
Similarly, if
{n} 6∈ A
, then
{g
(
n
)
} 6∈ A
. These again separately imply
g
(
n
) =
a
and g(g(n)) = a. So we find g(a) = a, which is again a contradiction.
Corollary. It is impossible to grade programming homework.