A user-friendly Introduction to (un)Computability and Unprovability
via “Church’s Thesis” Part II
This is Part II of our Uncomputability notes.
We introduce “half-computable” relations Q(⃗x) here.
These play a central role in Computability.
The term “half-computable” describes them well: For each of these relations there is a URM M that will halt precisely for the inputs ⃗a that
make the relation true:
i.e., ⃗a ∈ Q or equivalently Q(⃗a) is true.
For the inputs that make the relation false — ⃗b ∈/ Q— M loops forever.
That is, M verifies membership but does not yes/no-decide it by halting and “printing” the appropriate 0 (yes) or 1 (no).
Intro to (un)Computability via URMs—Part II © by George Tourlakis
2
Can’t we tweak M into M′ that is a decider of such a Q?
No, not in general! For example, the halting set K has a verifier
Right? x ∈ K ≡ φx(x) ↓≡ U(P)(x,x) ↓.
So any program MYX for the partial recursive λx.U (P ) (x, x) is a verifier
for x ∈ K. See also 0.1.2 below.
But we KNOW that x ∈ K has NO decider!
Since the “yes” of a verifier M is signaled by halting but the “no” is signaled
by looping forever,
the definition below does not require the verifier to print 0 for “yes”. Here “yes”
equals “halting”.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.1. Semi-decidable relations (or sets) 3 0.1. Semi-decidable relations (or sets)
0.1.1 Definition. (Semi-recursive or semi-decidable sets)
A relation Q(⃗xn) is semi-decidable or semi-recursive —what we called suggestively “half-computable” above—
iff
there is a URM, M, which on input ⃗xn has a (halting!) computation iff ⃗xn ∈ Q.
The output of M is unimportant!
A less civilized, but more mathematically precise way to say the above is: A relation Q(⃗xn) is semi-decidable or semi-recursive iff there is an f ∈ P
such that
Q(⃗xn) ≡ f(⃗xn) ↓ (1)
Clearly, an f ∈ P is some M⃗xn . Thus, M is a verifier for Q. y
The set of all semi-decidable relations we will denote by P∗.†
†This is not a standard symbol in the literature. Most of the time the set of all semi- recursive relations has no symbolic name! We are using this symbol in analogy to R∗—the latter being fairly “standard”.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
4
The following figure shows the two modes of handling a query, “⃗xn ∈ A”, by a URM.
A Decider
input
A Verifier
input
A URM for the problem
A URM for the problem
“yes”=print “0” “no”=print “1” and halt and halt
“yes”=just halt. Output is irrelevant
“no”=loop for ever
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.1. Semi-decidable relations (or sets) 5 Here is an important semi-decidable set.
0.1.2 Example. K is semi-decidable. To work within the formal definition (0.1.1) we note that the function λx.φx(x) is in P via the universal function theorem of Part I: λx.φx(x) = λx.U(P)(x,x) and we know U(P) ∈ P.
Thus x ∈ K ≡ φx(x) ↓ settles it. By Definition 0.1.1 (statement labeled (1))
we are done.
0.1.3 Example. Any recursive relation A is also semi-recursive. That is,
R∗ ⊆ P∗
Indeed, intuitively, all we need to do to convert a decider for ⃗xn ∈ A into a verifier is to “intercept” the “print 1”-step and convert it into an “infinite loop”,
k: gotok
By CT we can certainly do the whole thing via a URM implementation.
A more elegant way (which still invokes CT) is to say, OK: Since A ∈ R∗, it follows that cA, its characteristic function, is in R.
Define a new function f as follows:
0 if cA(⃗xn) = 0
f(⃗xn) = ↑ if cA(⃗xn) = 1
This is intuitively computable (the “↑” is implemented by the same “piece of
code” as above).
Hence, by CT, f ∈ P. But
⃗xn ∈A≡f(⃗xn)↓
because of the way f was defined. Definition 0.1.1 rests the case.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
6
One more way to do this: Totally mathematical (“formal”, as people say
incorrectly†) this time! OK,
f(⃗xn) = if cA(⃗xn) = 0 then 0 else ∅(⃗xn)
That is, using the sw function that is in PR and hence in P, as in c A ( ⃗x n ) 0 ∅ ( ⃗x n )
↓↓↓
f(⃗xn) = if z = 0 then u else w
∅ is, of course, the empty function which by Grz-Ops can have any number of
arguments we please! For example, we may take ∅ = λ⃗xn.(μy)g(y, ⃗xn)
where g = λy⃗xn.SZ(y) = λy⃗xn.1.
In what follows we will prefer the informal way (proofs by Church’s Thesis)
of doing things, most of the time.
An important observation following from the above examples deserves the- orem status:
†“Formal” refers to syntactic proofs based on axioms. Our “mathematical” proofs are mostly semantic, depend on meaning, not just syntax. That is how it is in the majority of MATH publications.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.1. Semi-decidable relations (or sets) 7 0.1.4 Theorem. R∗ ⊂ P∗
Proof. The ⊆ part of “⊂” is Example 0.1.3 above.
The ̸= part is due to K ∈ P∗ (0.1.2) and the fact that the halting problem
is unsolvable (K ∈/ R∗).
So, there are sets in P∗ (e.g., K) that are not in R∗.
What about K, that is, the complement
K =N−K ={x:φx(x)↑}
of K ? Is it perhaps semi-recursive ( verifiable)?
Intro to (un)Computability via URMs—Part II © by George Tourlakis
8
The following general result helps us handle the above question.
0.1.5 Theorem. A relation Q(⃗xn) is recursive iff both Q(⃗xn) and ¬Q(⃗xn) are semi-recursive.
Before we proceed with the proof, a remark on notation is in order. In “set notation” we write the complement of a set, A, of n-tuples as A.
This means, of course, Nn − A, where
Nn =N×···×N
n copies of N
In “relational notation” we write the same thing (complement) as
¬A(⃗xn )
Similarly,
“set notation”: A ∪ B, A ∩ B
“relational notation”: A(⃗xn) ∨ B(⃗ym), A(⃗xn) ∧ B(⃗ym)
Back to the proof.
Proof. We want to prove that some URM, N, decides ⃗x n ∈ Q
We take two verifiers, M for “⃗xn ∈ Q” and M′ for “⃗xn ∈ Q”,† and run them —on input ⃗xn— as “co-routines” (i.e., we crank them simultaneously).
If M halts, then we stop everything and print “0” (i.e., “yes”).
If M′ halts, then we stop everything and print “1” (i.e., “no”).
CT tells us that we can put the above —if we want to— into a single URM,
N.
†We can do that, i.e., M and M′ exist, since both Q and Q are semi-recursive. Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.1. Semi-decidable relations (or sets) 9 0.1.6 Remark. The above proof handled only the “if” direction. For the “only
if” this is trivial:
R∗ is closed under complement (negation) as we showed way back in a pre- vious Note.
Thus, if Q is in R∗, then so is Q, by closure under ¬. By Theorem 0.1.4, bothofQandQareinP∗.
0.1.7 Example. K ∈/ P∗.
Now, this (K) is a horrendously unsolvable problem! This problem is so
hard it is not even semi-decidable!
Why? Well, if instead it were K ∈ P∗, then combining this with Exam- ple 0.1.2 and Theorem 0.1.5 we would get K ∈ R∗, which we know is not true.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
10
0.2. Unsolvability via Reducibility
We turn our attention now to a methodology towards discovering new unde- cidable problems, and also new non semi-recursive problems, beyond the ones we learnt about so far, which are just,
1. x∈K,
2. φi = φj (equivalence problem) 3. and x ∈ K.
In fact, we will learn shortly that φi = φj is worse than undecidable; just like K it too is not even semi-decidable.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.2. Unsolvability via Reducibility 11 The tool we will use for such discoveries is the concept of reducibility of
one set to another:
0.2.1 Definition. (Strong reducibility) For any two subsets of N, A and B, we write
A ≤m B†
A≤B (1)
or more simply
pronounced A is strongly reducible to B, meaning that there is a (total) recur-
sive function f such that
x ∈ A ≡ f(x) ∈ B (2)
We say that “the reduction is effected by f”.
The last sentence has the notation A ≤f B.
In words, A ≤m B says that we can algorithmically solve the problem x ∈ A if we know how to solve z ∈ B. The algorithm is:
1. Given x.
2. Given the “subroutine” z ∈ B.
3. Compute f(x).
4. Give the same answer for x ∈ A (true or false) as you do for f(x) ∈ B.
†The subscript m stands for “many one”, and refers to f. We do not require it to be 1-1, that is; many (inputs) to one (output) will be fine.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
12
When A ≤m B holds, then, intuitively,
“A is easier than B to either decide or verify”
since if we know how to decide or (only) verify membership in B then we
can decide or (only) verify membership in A: “x ∈ A?”
All we have to do is compute f(x) and ask instead the
question “f(x) ∈ B” which we can decide or verify. This observation has a very precise counterpart (Theorem 0.2.3 below).
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.2. Unsolvability via Reducibility 13 0.2.2 Lemma. If Q(y,⃗x) ∈ P∗ and λ⃗z.f(⃗z) ∈ R, then Q(f(⃗z),⃗x) ∈ P∗.
Proof. By Definition 0.1.1 there is a g ∈ P such that
Q(y, ⃗x) ≡ g(y, ⃗x) ↓ (1)
Now, for any ⃗z, f(⃗z) is some number which if we plug into y in (1) we get an equivalence:
Q(f (⃗z), ⃗x) ≡ g(f (⃗z), ⃗x) ↓ (2)
But λ⃗z⃗x.g(f(⃗z),⃗x) ∈ P by Grz-Ops. Thus, (2) and Definition 0.1.1 yield Q ( f ( ⃗z ) , ⃗x ) ∈ P ∗ .
0.2.3 Theorem. If A ≤g B in the sense of 0.2.1, then (i) ifB∈R∗,thenalsoA∈R∗
(ii) ifB∈P∗,thenalsoA∈P∗ Proof.
(i) The assumption says that z ∈ B is in R∗. So is g(x) ∈ B by Grz. Ops. (Way back). But x ∈ A ≡ g(x) ∈ B, so x ∈ A is in R∗.
(ii) Letz∈BbeinP∗.
By0.2.2,soisg(x)∈B. Butthissaysx∈A.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
14
0.2.4 Corollary. If A ≤ B in the sense of 0.2.1, then (i) ifA∈/R∗,thenalsoB∈/R∗
(ii) ifA∈/P∗,thenalsoB∈/P∗
Taking the “contrapositive”, we have at once:
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.2. Unsolvability via Reducibility 15
We can now use K and K as a “yardsticks” —or reference “problems”— and discover new undecid- able and also non semi-decidable problems.
The idea of the corollary is applicable to the so-called “complete index sets”.
0.2.5 Definition. (Complete Index Sets) Let C ⊆ P and A = {x : φx ∈ C}. A is thus the set of ALL programs (known by their addresses) x that com-
pute any unary f ∈ C:
Indeed,letλx.f(x)∈C.Thusf=φi forsomei.Theni∈A. But this is true of all φm that equal f.
We call A a complete index (programs-) set.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
16
We embark on several examples, but first note the FORM of S-m-n Theorem that we will be using going forward:
0.2.6 Theorem. (S-m-n in practice) If ψ ∈ P has two arguments, then there is a unary h ∈ R such that
for all x, y.
Proof. Fix an i such that ψ(x, y) = φ(2)(x, y), for all x, y. i
By S-m-n, we have a recursive λix.S1(i,x) such that φ(2)(x,y)=φ 1 (y)
for all i,x,y.
But i is fixed.
Thus λx.S1(i,x) is the “h” we want.
ψ(x, y) = φh(x)(y) (1)
i S1 (i,x)
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.2. Unsolvability via Reducibility 17 0.2.7 Example. The set A = {x : ran(φx) = ∅} is not semi-recursive.
Recall that “range” for λx.f(x), denoted by ran(f), is defined by {x : (∃y)f(y) = x}
We will try to show that
K≤A (1) If we can do that much, then Corollary 0.2.4, part ii, will do the rest.
Well, define
Here is how to compute ψ: • Given x, y, ignore y.
0
ψ(x, y) =
↑
if φx(x) ↓ if φx(x) ↑
(2)
• Call φx(x) —that is, U(P)(x,x),
• If the call ever returns, then print “0” and halt everything.
• If it never returns, then this agrees with the specified in (2) behaviour for ψ(x, y).
By CT, ψ is in P, so, by the S-m-n Theorem, there is a recursive h such that ψ(x, y) = φh(x)(y), for all x, y
You may NOT use S-m-n UNTIL after you have proved that your “λxy.ψ(x,y)” is in P.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
18
We can rewrite this as,
0 if φx(x) ↓
φh(x)(y) = ↑ if φx(x) ↑ (3)
or, rewriting (3) without arguments (as equality of functions, not equality of function calls)
λy.0 if φx(x) ↓
φh(x) = ∅ if φx(x) ↑ says x ∈ K
In (3′), ∅ stands for λy. ↑, the empty function. Thus,
bottom case in 3′
(3 )
′
h(x) ∈ A iff ran(φh(x)) = ∅ iff φx(x) ↑ Theabovesaysx∈K≡h(x)∈A,henceK≤h A,andthusA∈/P∗ by
Corollary 0.2.4, part ii.
Def
K = {x:φx(x)↓}
Def
K = {x:φx(x)↑}
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.2. Unsolvability via Reducibility 19 Lecture #15, Nov. 9.
0.2.8 Example. The set B = {x : φx has finite domain} is not semi-recursive. This is really easy (once we have done the previous example)! All we have
to do is “talk about” our findings, above, differently!
We use the same ψ as in the previous example, as well as the same h as above, obtained by S-m-n.
Looking at (3′) above we see that the top case has infinite domain, while the bottom one has finite domain (indeed, empty). Thus,
bottom case in 3′
h(x) ∈ B iff φh(x) has finite domain iff φx(x) ↑ Theabovesaysx∈K≡h(x)∈B,henceK≤B,henceB∈/P∗ byCorol-
lary 0.2.4, part ii.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
20
0.2.9 Example. Let us mine twice more (3′) to obtain two more important undecidability results.
1. Show that G = {x : φx is a constant function} is undecidable.
We (re-)use (3′) of 0.2.7. Note that in (3′) the top case defines a constant
function, but the bottom case defines a non-constant. Thus h(x)∈G≡φh(x) =λy.0≡topcasein3′ ≡x∈K
Hence K ≤ G, therefore G ∈/ R∗.
2. Show that I = {x : φx ∈ R} is undecidable. Again, we retell what we can read from (3′) in words that are relevant to the set I:
∅ ∈/ R !
h(x)∈I ≡ φh(x) =λy.0≡x∈K
Thus K ≤ I, therefore I ∈/ R∗.
In Notes #8 we will sharpen the result 2 of the previous example.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.2. Unsolvability via Reducibility 21
0.2.10 Example. (The Equivalence Problem, again) We now revisit the equivalence problem and show it is worse than unsolvable (cf. Notes #6):
The relation φx = φy is not semi-decidable.
By 0.2.2, if the 2-variable predicate above is in P∗ then so is λx.φx = φy,
i.e., taking a constant for y.
Choose then for y a φ-index for the empty function. In short,
If the equivalence problem is VERIFIABLE, then so is
φx = ∅
Eq={x:φx =∅}={x:ran(φx)=∅}=A which says the same thing as
ran(φx) = ∅
We saw that this NOT SEMI-RECURSIVE in 0.2.7.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
22
0.2.11 Example. The set C = {x : ran(φx) is finite} is not semi-decidable.
Here we cannot reuse (3′) above, because both cases in the definition by cases —top and bottom— have functions of finite range.
We want one case to have a function of finite range, but the other to have infinite range.
Aha! This motivates us to choose a different “ψ” (hence a different “h”), and retrace the steps we took above.
OK, define
Here is an algorithm for g:
• Given x,y.
y
g(x, y) =
↑
if φx(x) ↓ if φx(x) ↑
(ii)
• Call φx(x) —i.e., call U(P)(x,x).
• If this ever returns, then print “y” and halt everything.
• If it never returns from the call, this is the correct behaviour for g(x,y) as well:
namely, we want g(x,y) ↑ if x ∈ K.
By CT, g is partial recursive, thus by S-m-n, for some recursive unary k we have
Thus, by (ii)
g(x, y) = φk(x)(y), for all x, y λy.y ifx∈K
φk(x) = ∅ othw
Intro to (un)Computability via URMs—Part II © by George Tourlakis
(iii)
0.2. Unsolvability via Reducibility 23 Hence,
k(x)∈C iffφk(x) hasfiniterange That is, K ≤ C and we are done.
bottom case in iii
iff x∈K
Intro to (un)Computability via URMs—Part II © by George Tourlakis
24
0.2.12 Exercise. Show that D = {x : ran(φx) is infinite} is undecidable.
0.2.13 Exercise. Show that F = {x : dom(φx) is infinite} is undecidable.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.2. Unsolvability via Reducibility 25 Enough “negativity”!
Here is an important “positive result” that helps to prove that certain rela- tions ARE semi-decidable:
0.2.14 Theorem. (Projection theorem; Part I) A relation Q(⃗xn) that is expressible as
Q(⃗xn) ≡ (∃y)S(y, ⃗xn) (1) where S(y, ⃗xn) is recursive is itself semi-recursive.
Q is obtained by “projecting” S along the y-co-ordinate, hence the name of the theorem.
Proof. Let S ∈ R∗, and Q be connected as in (1) of the theorem. Clearly,
(∃y)S(y, ⃗xn) ≡ (μy)S(y, ⃗xn) ↓
and we know that
Def
(μy)S(y,⃗xn) = (μy)cS(y,⃗xn), for all ⃗xn
(2)
(3)
Thus λ⃗xn.(μy)cS(y,⃗xn) is partial recursive by closure of P under UNbounded search. Thus so is λ⃗xn(μy)S(y,⃗xn) by (3).
Now (1) and (2) give
Q(⃗xn) ≡ (μy)S(y, ⃗xn) ↓ We are done by Def. 0.1.1.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
26
0.2.15 Example. The set A = {(x, y, z) : φx(y) = z} is semi-recursive.
Here is a verifier for the above predicate:
Given input x,y,z. Comment. Note that φx(y) = z is true iff two things happen: (1) φx(y) ↓ and (2) the computed value is z.
1. Given x, y, z.
2. Call φx(y) = U(P)(x,y).
3. If the call returns, then
• If the output of U(P)(x,y) equals z, then halt everything (the “yes” output).
• If the output of U(P)(x,y) does NOT equal z, then get into an infinite loop (the “no” case).
4. If the U(P)(x,y) ↑, then keep looping (say “no”, by looping). By CT the above informal verifier can be formalised as a URM M.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.3. Projection Theorem II 27 Lecture #16, Nov. 11.
0.3. Projection Theorem II
This section provides a new powerful tool AND proves the converse of Projection Theorem Part I.
How can we trace a (computation of a) URM ? Exactly in the same manner that we learnt to trace a
commercially available program such as C.
0.3.1. Computation simulating functions
GivenaURMMX⃗m where—withoutlossofgenerality— X1
we selected X1 as the output variable. Let all its variables be
inputs Non inputs
X1,…,Xm,Xm+1,…,Xn (1)
Intro to (un)Computability via URMs—Part II © by George Tourlakis
28
For any input ⃗am, M’s computation can be tabulated in a (potentially infinite) table —p.29 below— where for each y ≥ 0, row y contains the values of ALL the vari- ables in (1) as well the value of the Instruction Pointer IP —that points to the CURRENT instruction— at step y.
A “step” is the act of executing ONE instruction of M and reaching the next CURRENT instruction.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.3. Projection Theorem II 29
At step zero, (y = 0) the computation ponders the first instruction of M after the “I/O Agent” initialised the in- put variables and has set all non-input variables to zero.
The entries on the zeroth row are self-evident.
Table 1: M Simulation Table
y
IP
X1
X2
…
Xm
Xm+1
Xm+2
…
Xn
0
1
a1
a2
…
am
0
0
…
0
.
.
.
.
…
.
.
.
…
.
i
L
b1
b2
…
bm
bm+1
bm+2
…
bn
i+1
L′
b′1
b′2
…
b′m
b′m+1
b′m+2
…
b′n
.
.
.
.
…
.
.
.
…
.
The process for filling the table is algorithmic as fol- lows:
Going from row i to row i + 1 (Cf. p.10 in http:// www.cs.yorku.ca/~gt/papers/NOTES-2-URMs.pdf):
1.LpointstoXk ←r. Thenb′k =rwhileb′j =bj for j ̸= k. Also L′ = L + 1.
2.LpointstoXk ←Xk+1. Thenb′k =bk+1while b′j = bj for j ̸= k. Moreover L′ = L + 1.
3.LpointstoXk ←Xk −. 1. Thenb′k =bk −. 1while b′j = bj for j ̸= k. Moreover L′ = L + 1.
4.Lpointstostop. Thenb′j =bj forallj̸=n. More- over L′ = L.
5.Lpointstoif Xk =0gotoRelsegotoQ. Then b′j =bj forallj̸=n. MoreoverL′ =ifbk = 0 then R else Q.
Intro to (un)Computability via URMs—Part II © by George Tourlakis
30
Note that at “time” y each Xj and the IP function hold a value that depends on the initial ⃗am —and on y.
. Thus we associate with each Xj and with the IP a TOTAL function —λy⃗am.fj(y,⃗am) and λy⃗am.IP(y,⃗am).
Since I can produce each such function-value, for the Xj and IP —for example, by hand— in the mechanical way indicated,
by CT, each such function fj and IP is RECURSIVE. In particular, f1 = MX⃗m ∈ R and λy⃗am.IP(y,⃗am) ∈
R.
Important!
X1
0.3.1 Theorem. With reference to the URM M that we “traced” above, we have that MX⃗m halts for input ⃗am
, where k is the label of stop
X1
iff there is some step value y where M makes its stop
instruction current. That is
(∃y)IP(y,⃗am) = k
Intro to (un)Computability via URMs—Part II © by George Tourlakis
0.3. Projection Theorem II 31
0.3.2 Theorem. (Projection Theorem Part II) IF Q(⃗xm) is semi-recursive, THEN there is a recursive P(y,⃗xm)
such that
Q(⃗xm) ≡ (∃y)P (y, ⃗xm) Proof. By Definition 0.1.1,
Q(⃗am) ≡ g(⃗am) ↓
where g ∈ P.
Let then g = MX⃗m.
By 0.3.1,
g(⃗am) ↓≡ (∃y)IP(y,⃗am) = q, where q labels stop in M
But IP(y,⃗am) = q is recursive so we may take it as the “P(y,⃗xm)” we want.
X1
Intro to (un)Computability via URMs—Part II © by George Tourlakis