Limits of
Computation
8 – Our first non-computable problem Bernhard Reus
1
A non-computable problem
THIS TIME
•
• we consider a decision problem:
the Halting Problem,
and prove it is WHILE- undecidable!
Deep Thought
we define formally what computability and decidability means (for WHILE)
“What is the Ultimate Answer to Life,
the Universe, and Everything?”
2
(a, b) ⇧ g we write b = g(a), that is, we put parentheses around a. have written f ((3, 2)) = 2, rather than f (3, 2) = 2. However it is c
Problems Revisited
(a, b) ⇧ g we write b = g(a), that is, we put parentheses around a. Thus above set of parentheses, and we shall also do so.
The range of a total or partial function from A into B is the set element is in argnivge(fn)s=et{–b ⇧yeBs|otrhneroe?)is a a ⇧ A such that f(a)
5 Elements of Computarnbg(ifl)i=ty{b⇧TB|hteheorerisya a⇧A such that f(a)=b}
•
notion of computability:
Chapter ?? set up our model WHILE of computation, Chapter 3 gave a we now narrow this down to our chosen
WHILE programs as input to other WHILE programs, and Chapter 4 existence of universal programs. We are now in a position to state and prove
Chapter ?? set up our model WHILE of computation, Chapter 3 gave a way to pass AA.3..34.4 Totallvveresrusupsarptaiarltfiuanlcftuioncstions
fundamental results of computability theory, including those that were inform WHILE programs as input to other WHILE programs, and Chapter 4 showed the
Any total function is also a partial function. For a partial function f : A ⇥ B in Chapter 1.
Any total function is also a partial function. For a partial functio
existence of universal programs. We are now in a position to state and prove some of the
happen that for all a ⇧3 A, f(a) is defined, i.e. dom(f) = A. In that case f is a Section 5.1 defines the notions of computable function and decidable set, happen that for all a ⇧ A, f(a) is defined, i.e. dom(f) = A. In tha
fundamental results of computability theory, including those that were informally proven
function.
related notions of semi-decidable and enumerable sets. Section 5.2 present
function.
There are two standard ways of obtaining a total function f from a partia
in Chapter 1.
Section 5.1 defines the notionsTofhceormepaurteabtlwe founscttaionndanrddwecaidyasbolefsoetb,tanidnitnhegtawototal function f fr
izer for WHILE programs. Section 5.3 proves that the halting problem is u
f : A ⇥ B⇥:
Section 5.4 proves that all properties of WHILE programs that depend only relatednotionsofsemi-decidafb:leAan⇥deBnum:erablesets.Section5.2presentsaspecial-
⇥
1. Remove all those elements of A on which f is undefined: Define f : dom
Functi
Remember
have written f ((3, 2)) = 2, rather than f (3, 2) = 2. However it is customary to
Forapartialfunctionf:A⇥B thedomainoffistheset
•
can we compute a given function of type
set of parentheses, and we shall also do so.
we restricted to problems of the form:
For a partial function f :A⇥B
the domain of f is the set dom(f) = {a ⇧ A|f(a) ⌅}
•
InL-cdaasteaf➝iLs-tdoattal, ?dom(f) = A.
⇥
⊥
dom(f) = {a ⇧ A|f(a) ⌅}
•
(i.e. can we compute whether a given
5canwEeldecmidenmtemsboerfshCipoinmaspetu
tabilityTheory
In case f is total, dom(f) = A.
The codomain of a total or partial function from A into B is t
The codomain of a total or partial function from A into B is the set B. The range of a total or partial function from A into B is the s
⇥
izer for WHILE programs. Sgecrtaimon’s5i.n3ppurto-voeustpthuattbtheheahvaioltuinrgapreroubnledmeciisdaubnldee.ciSdaecbtleio.n 5.5 proves some p
1. Remove all those elements of A on which f is undefined: D by f (a) = f(a) for all a ⇧ dom(f).
Section 5.4 proves that all prodpeecridtiaebsloef aWnHdIsLeEmpi-rdoegcriadmasbltehastetdse,paend oSnelcytionth5.e6psrho-ows that the halting
some WHILE program:
Definition 5.1.1 A partial function f : ID ID is WHILE computable i
by f (a) = f(a) for all a ⇧ dom(f).
2. Add a new element to B and let that be the result whenever f is u
gram’s input-output behaviour are undecidable. Section 5.5 proves some properties of
semi-decidable. Section 5.7 proves some properties of enumerable and sem
WHILE Computability a⇧A\dom (f).
Define f :A⇥(B⌃{ }) by: f (a)=f(a) for all a⇧dom(f), and f ( 2. Add a new element to B and let that be the result whe
decidable and semi-decidable sets, and Section 5.6 shows that the halting problem is
sets.
a ⇧ A\dom(f ).
sets.
88 Define f : A ⇥8(BAn⌃Un{d ec}id)abbley(N:onf-co(map)uta=blef) P(raob)lemfor all a ⇧ dom( semi-decidable. Section 5.7 proves some properties of enumerable and semi-decidable
Definition 8.1 A partial function f : D → D is WHILE-computable if there is A.3.5 Equality of fu⊥nctions and partial values
5.1 Computability, decidability, enumerability
a WHILE-program p such that f = pWHILE, in other words if f is equal to the
The slogan here is:
Recall that functions are just certain sets, and that two sets are equal if and o
semantics of p (we can also say “if p implements f ”).
A.3.5 Equality of functions and partial values
5.1 Computability, decidability, enumerability
As mentioned earlier, a function is henceforth called computable if it is c
contain the same elements. This implies that two total functions f,g : A ⇥ B
sRomecealWl tHhIaLtEfpurnocgtriaomn:s are just certain sets, and that two sets are eq if and only if they are the same sets of pairs. Equal total functions f and g th
Slogan: a WHILE-computable function on trees is one that
As mentioned earlier, a function is henceforth called computable if it is computed by
cofn(ta)in= gt(hae) fsoarmalel ael⇧emA.ents. This implies that two total functions
A WHILE-computable (partial) function on trees is one that can be implemented in WHILE.
can be implemented in WHILE.
Similarly, two partial functions f,g : A ⇥ B are equal i dom(f) = dom( if and only if they are the same sets of pa⇥irs. Equal total function
The above definition of f being WHILE-computable means in more detail that for
WHILE program p such that f = [[p]], i.e. for all d, e ⇥ ID: all a⇧dom(f):f(a)=g(a), i.e. i for all a⇧A:
Definition 5.1.1aAnypda,reti∈alDfu(f(noacrt)ailo=lntregfe(s:adID)afn odreID)a:lliasso⇧WHAI.LE computable i there is a
WHILE program p such that f = [[p]]W,HiI.LeE. for all d, e ⇥ ID:
1.S1iIm.f fil((ad)r)⇤ly=a,n⇤tdwtgoh(aemp)n⇤ae;[[rapotn]ri]s(adlt)hf=autn⇤fc.itsiounsdeffi,nged: Aat⇥d B are equal i dom
1. If f (d)↑ then p (d)↑ ⇥ Notation
Whenever f applied to d is undefined, then so is the semantics of p, in other all a2⇧. fd(oam)⌅(afn)d:gf(a(m)a⌅)ea=ndsgft(ha(a))t,=fi.iegs.(adi)e .fifnoerdaltl a ⇧ A:
2. If f (d) =e⇥ ID then [[p]](d) =e.
1. If f(d)=⇤ then [[p]](d)=⇤.
words program p does not terminate when run on input d.
2. Iff(d)=e⇥IDthen[[p]](d)=e. 2. If f (d) = e th1e.n fp(a)⇤ a(nd)d= ge(a)⇤; or
WHILE
A set A will be called decidable if the membership question for A can be an Whenever f applied to d equals e, then so does semantics of p applied to d, in
2. f (a)⌅ and g(a)⌅ and f (a) = g(a).
program that always terminates. If the program possibly loops on element
A set A will be called decidable if the membership question for A can be answered by a other words program p terminates when run on input d and produces e as output.
program that always terminathese.sIefttwheillpbroegcramlledpossesmibil-ydelocoidpasbolne.elements outside A,
As we can encode numbers in WHILE’s data type, we know that a WHILE-
of computation that use the natural numbers as data type (this is quite common).
4
the set will be called semi-decidaWble. will show semi-decidability equivalent to enumerability, where a set computable partial function on natural numbers is one that can be implemented in
We will show semi-decidability equivalent to enumerability, where a set A is called
WHILE. ThiseinsuimpeoratabnltewihfenthceormepaisrinsgomWHeILpEro-cgormamputtahbialittyliwsittsh oatlhlear nodtionsly the elements o
enumerable if there is some program that lists all and only the elements of A in some
order. This allows repetitions, and does not necessarily list A’s elements in
A decision problem A with domain D corresponds to a set A ⊆ D of trees. The order. This allows repetitions, and does not necessarily list ’s elements in any specific
A decision problem A with domain D corresponds to a set A ⊆ D of trees. The
uniform question problem for A is the following: Isagivenelementd∈Din A?
Or in other words: Given d ∈ D, does d ∈ A hold? Note how this is a problem
in our sense: it is uniform, the input type is well defined (D) as well as the output type which has to allow for answers ‘yes’ and ‘no’ (‘true’ and ‘false’) and is thus the type of Boolean values. Elements of each of both types are finite and precisely describable.
WHILE decidability
able by an effective procedure, as we know we use WHILE as effective procedures:
We can now instantiate the generic definition of a problem computable or decid-
A decidable set (or a decidable problem) is one for which the membership test can be computed by a WHILE-program that always terminates.
These definitions can also be given more precisely and formally:
Definition8.2 AsetA⊆DisWHILE-decidableif,andonlyif,thereisaWHILE- program p such that pWHILE (d)↓ (meaning pWHILE (d) is defined) for all d in D, and, moreover, d ∈ A if, and only if, pWHILE (d) = true.
Note that in the (older) literature, when computability is defined in terms of natural nuSmlobegracno:mapuWtatHioIn,LaEd-edciedacbidleasbetleis soeftetnocrallpedroa brelceumrsivoenset.rees is one for
which the membership test can be implemented in WHILE.
(formally)
5
Our first Non-computable Problem
6
8.2 The Halting Problem for WHILE
89
8.2 The Halting Problem for WHILE
Let us look at the following problem which is about WHILE-programs (represented
A decision problem:
as elements of D, we already know how to encode programs as data so this is not a problem).
Definition8.3 TheHaltingproblem—assetHALT⊆D—isdefinedasfollows: HALT={[p,d]∈D| pWHILE(d)↓}
What does the problem say informally speaking, given as a class of (uniform) ques- tions? Well, the question is this:
WHILE-program as data WHILE-data
Given a WHILE-program p (as data) and a value d ∈ D, does program p terminate if we run
it on input d?
the list (and thus the
program) are encoded but
Note again the uniformity, the answer must be given for an arbitrary program and
we drop the encoding
data. We also have a problem about two pieces of information here, the program and
brackets
its input, but we can pair them together into one input tree in the way we already encountered for otherWHILE-programs using the encoding of pairing (p,d) as list [p,d] which can be itself encoded in D. We drop the encoding brackets from the list to improve readability. We will drop those encoding brackets most of the time in
the following chapters too.
We will show in this section that the set HALT is not WHILE-decidable in the sense
explained earlier (Definition8.2). This is equivalent to showing that the function halt defined below is not computable by a WHILE-program. In other words, the (total) function
7
halt(a) = true if a = [p,d] and pWHILE(d) ↓ false otherwise
Big Question:
(which is the membership test for the Halting set HALT) is not computable by a
WHILE-program.
It should be clear that it would be really useful if we could compute/solve this prob-
lem. A compiler could then check if we had inadvertently written a non-terminating program for some specific input and warn us like a type checker warns us about incompatible types when we have used expressions in an ill-typed way.
It is desirable to be able to recognise undecidable problems. Nobody wants to
star
It should be pointed out that there is still a considerable amount of research going on how to find out whether a program might not terminate for some input. Termination checkers have been recognised as a useful tool even if they cannot work for all input
is HALT WHILE-decidable
t wor
king
for a non-computable problem. One would like to avoid wasting time on that. It is of course not always easy to find out whether a problem is undecidable and, maybe quite surprisingly, there is an abundance of undecidable problems. We will soon present more of them in Chap. 9. It turns out that some of them can be easily recognised.
ona
proje
ct tha
sto
devel
t seek
tes
the
s
opa
pro
gra
mth
at
co
mpu
olut
?
ion
8
About the Halting Problem
• Solving the Halting Problem would be most useful, e.g. a compiler could check for termination of function calls and warn about non-termination like a type checker warns about incompatible types.
• Note that simply interpreting the program on its input does not work: if the interpreter does not terminate, one cannot return the answer ‘no’.
9
Proof of the Undecidability of the
IDEA
Halting Problem
• Assume a WHILE-program h exists that DOES solve the Halting Problem.
• With h’s help write a new WHILE-program r
• establish a contradiction
• so that the assumption that h exists must be wrong.
Establishing a contradiction to destroy a robot or computer is a very popular SciFi plot line (a.k.a. Logic Bombs).
10
The Barber of Seville Paradox
strictly speaking not a “paradox” as the contradiction can be resolved.
The Barber of Seville says:
http://www.wno.org.uk/4299
“In my town Seville, I shave all men who do not shave themselves. Those who actually shave themselves, I do not shave.”
This is a version of Bertrand Russell’s paradox (Famous Welsh logician, 1872-1970)
11
The Barber of Seville Paradox
The Barber of Seville says:
“In my town Seville, I shave all men who do not shave themselves. Those who actually shave themselves I do not shave.”
Does the barber shave himself?
(note that he lives in Seville and is a man):
No implies he shaves himself
Yes implies he does not shave himself
http://www.wno.org.uk/4299
contradiction
“paradox” can be resolved by saying such a Barber does not exist :-). Does not contradict any laws of nature.
12
The Barber of Seville Paradox as Diagonalisation
diagonal
man of Seville no
shaves 1 2 3 4 5 6 … 3466 3467 …Barber’s row
1 yes yes no yes no no
2 nonoyesnonoyes
3 no yes no no no no
4 yes yes no no yes yes
5 nonononono no
6 yesyesnononoyes
no no no yes no yes yes yes no no yes yes
is the negated diagonal. It thus
can’t be one of the rows of the table, so Barbercan’t be a male
… … … … … … … … …
3466 yes yes no no yes yes 3467
no yes yes no yes yes
…
Barber’s row no yes yes yes yes no
yes
yes no
… no yes …
yes from Seville,
but he is!
contradiction
What is the table entry (x,y) ?
At row x and column y we put yes if man # x shaves man # y and false otherwise.
13
More on that theme
http://xkcd.com/468/
14
man of Seville no.
The problem is the implicit self-reference.
if Y then
true if [[p]](d) if [[p
h alt( , )= ⇥ true if [[p]](d)
)
⇥
mf t
a
e
t
i
;
e
a C
o
=
n( e
o (
mt W
s e
t a u
un d
m
d mr
h B
u i i i
e
s
d
:
e
o
maoe
h
c
s n o
c
s
td l
u ro
c
Tr a
a c q
eh m
o j
6 7
76
16
false [[q]](p,d) = WHILE
[[q]](p,d)=
In iosthneort wcoomrtdprsu,temdobryeifca[on[pyn]c]p(idsroe)g lyr,am“D. oes r (r
while Y do Y f:a=lsYe; if [[p]](d) = ⇥(*
false if[[p]](d)= go through r and inteisrpnroet citowmiptuhtredasbyinapnuyt.pIrnogthrae
[[q]](p,d) =
writefaYlse if[[p]](d)=⇥ (*
Proof. Suppose halt were computed by some progra By assumption this has the form: q = read
brackets from the program arguments, so we do no
value
Proof. Suppose halt were compu P,D; C; wr he sake of read
By assumption this has the form: q = r
terminating loop but instead terminates with re
15 = false on input (r,rC).onTchlusiocnom: m[[ra]]n(rd)w=hi⇥lemYus Thus every possibility leads to a cont Thus every possibility leads to a contradiction. The on was the existence of a program q that comp false or, ignoring the result, rWHILE(r) ↓. Bu
program r will term=infatlesoenoninipnupturt,(arn,ro)t.heTrhcuosnct
was the existence of a program q that was the existence of a program q that computes halt, so supp6osed to be false? Indeed it was, and theref
ThAusceovnesreyqupeonscspeibriosilgitrhyaamltearldlswptirololgatreacromnstinrmaadtyeicbotienonrien.p
which means by assumption (h decides the H ThiAs acrognusmeqenuteniscceloisetlhyartelaltledprtogtrhaempsamraadyoxbe A conseqwueansctehies tehxaisttaelnlcperogframTphsroumgsraeayvmebreyqrptehpoarsestsibecnioltmietydpulaetsaedeslseht
This argumteserinmtilinasarctTleoxhsaweimlsyhpaerlenegl:uart“mueTndehntewtobitstahrcebliopensrapersluahydtarovrexe,lesaistjnueodsfotmthtoahetotrhsewemwpoahartdroi was the existence of a program
7
er of the two enrtpiountsr[[,r]a](nro) t
nwwille yaireldobYv=io give r as input m q will yield
=tetrrmuienaotne winhpe rseatcohaescconmtrmaa
what happens if
n it reaches co
minute, was Y and while Y
mt.woqatssheartiocnos [[ n[.r, r ] must be
yuriestlhdebYeo=tthretureuo.ef to
alting problem)
⇥ must be tr eBsncupotrmotmghriasnmdimqwphwli
rams may be r
command wh d to the parado HILE (r ) ↓. Thi
Tmhur,swchoemnmitarena hileYdoY
nput r, anoth es just those w
e then. In this
netrtarduiec.tiBonu.t thi on input r, a her contradicti s to a contradi
of
ppl’sy
Apply program q to CliefarYlytohneenor the other o
Halting Problem existed:
h read A {B} write C then define r as:
in other words:
HAL
d
By assumption this has the form: q = read
read X;
y
T
2. After the first assignme[[nqt]](opf,dth)e=
A
pro
and itnsgdaptraorgerparmesern,tbatuioilnt fromfoqr:t
n
gra
ing progra m r, built from
value d
Now let us see what happens
Proof
U
read X; false if [[p]](d Apply program q to inp
ing program r, built from q: true if [[p]](d read X;
1. Initia[[lqly]],(pw,de)r=ead in the input and
r to itself: X = r.
d
e
c
id
m
Bvyalausesu[mri,pfrti]oY.nthiesnhas the form: q
a
q whileYdoY:=Y;
to
inp
if Y then
If [[r]](r) , then program q
Does whihleolBdYy? adsosumY p:ti=onYt Assume a program deciding the 3. inTghepnrobglroacmk Br,isbeuxiletcfurotemd wq:hich d
write Y whileYdoY:=Y; (*
write Y does program r pltiieosnt).hTaht epreraofgterra,imnvgarpi,arobwglerhaeCmncrio,tn
write Y read X; terminate wh(en*run
WHILE
ut
(
b
i
l
i
t
X
,
X
);
(
and derive a contradiction. Then h cannot exist.
If [C[ro]](nrc)l u,stihoenn: p[[rro]g](rra)m=q⇥wilml if then
Y = C A=pplhy progr[arm, rq ].to input (X read X;
on input r, a contradiction.
NiofwYlettheuns see what happens 4. Next, is executed andraofgter
tussenr 5. F ws,
= Thu
elf: X tero
oth arlyproongeroarmthre wotihllerteorfmthineatwteooanssi
First Iafss[[urm]](er)Y ,isthinednepedrotgruraem, thqe Now let us see what happens if we iIf [[r]](r) t,htehnen
progra
r]](r) lo,otph,esnopwroegkrnaomwqthwatilrl ydioeelds nYot pTlihesutsheavteprryogproasmsirb,ilwithyenleiatd
rtoitself:X=r. Nowletussee WHILrE doesn’t terminate
plies that program r, whe
r (r) = ⊥. But, hang on a
at program r, when it reaches comm
wasonCthlieneaprleuyxtoirsnt,eeaonrctorehnetotorofaittadhseiecprlftr:oiofXngt=h.rear else r terminates
WHILE it waosn. Iinpthuist cra,seaYco=ntrhadictio
on input r, a contradiction. Clearly one o
6
Y:=C Apply p
Now let us see what
with r as input?
happ ⇥m
r read X {
A:= [ X, X ];
B;
Y:= C;
Cle while Y { Y:=Y }
}
write Y
Now le
r to its
If [[ plies th
Y = true means h says termination but r Conclusion: [[r]](r)= while Y do Y := Y; ee what happens iiffweY gtihv
r to itself: X = r.
or the bwehaivlees oltoheorpwisteh. at follo
wrritteoYitself: X=r.
while fYa=lfalseemeoans hinsapysunotn-(term,rina)t.ion
=r.
rue oCrlneaort.ly one or the oth
butrbehavesotherwisrei.teY Clearly one or the
by assumption (h decides the H Conclusion: [[r]](r)=
A consequence is that all prog
Concluspiolinefs: t[h[ra]t](prr)o=gra⇥mtmrh,uewIsnfhte[[brn]e]i(trtr)re ua,ect.h 7=falseoninput(r,r). ThuWs
with input r, in other words r on in=putfar,lasecoonntrpailndieipcsuttitohna(.trp,ro)g.ra
This argument is closely relate
= false on input (r,r). Thus command w program r will terminate on i similar example: “The barber shav
Ok, maybe this means Y is fals
Conclusion: [[r]o](nr)in=pu⇥trm,uastcob program r will terminate program r will terminate on input r, anot
Thus every possibility lead
Yd
q:
if we give r )
afterwards X c
) =t⇥rue if [[p ut (X,X); (* program, A:=[
input (X,X)
false if [[p f the two ass * Does progr
= read P,D; (*L
will yield Y e;hciisdheassthteheHfaolrtmi
(*T LoopifXst
btuaiilnt sfrtohme qre: sul reaches com
Terminate if
,X); (* Does
if we givera rawmaqrdstoY i=nphut
ens if we give
ust be true.
as input to th
(* Loop if
we have to dist
(* Termina
o Y := Y;
s command w f the two asser
Proof
HALT
Undecidability
sSimoilawr hexicahmepvle: r“cTahseebwa7rbeecr oshnasviedsejru,st This argument
• The proof was using the Barber paradox technique.
• Can we also understand (reformulate) this as a proof by diagonalisation?
• In order to do that, first note that we can enumerate all WHILE-programs (like we could enumerate all men in Seville). Why is that?
of
similar example: “
’s
6A consequence is that all programs
r WHILE (r ) ↓.
This argument is clos6ely related to th
similar example:7 “sTimheilbaarrebxearmshpalve:es“jTushtetbhaorsbeewr
A consequence
may be represented
hsohadvoensojtusthatvheost e paradoxes of mat is that all progra
wtehoaselwahyo sdogentota is closely related t
The barber shaves
The Halting Problem as Diagonalisation • How does r behave for
arbitrary input programs X:
• If X run on input X terminates,
r does not terminate.
• IfXrun on inputXdoes not
terminate, r does terminate.
• So r behaves a bit like the Barber.
read A {B} write C
assumed to decide the Halting Problem
r read X {
A:= [X,X]; B;
Y:= C;
while Y {
Y:=Y }
} write Y
17
The Halting Problem as Diagonalisation
doesprogramA WHILEprogramBno terminate when
input is program 1 2 3 4 5 6 … 3466 3467 … B?
1 2 3 4 5 6
yesyesnoyesno no no no
r’s row is the negated diagonal. It thus
can’t be one of the rows of the table, so r can’t be a WHILE program,
but it is!
nonoyesnonoyes noyesnono no no yes yes no no yes yes no no no no no no yesyesnononoyes
no yes no yes yes yes no no yes yes … … yes yes
yes no
no yes …
“r terminates if its argument (program) does not terminate when it is given itself as input; otherwise r does not terminate.”
… … … … … … … 3466 yes yes no no yes yes 3467
no yes yes no yes yes
…
r’s row no yes yes yes yes no
…
diagonal
contradiction
18
r
WHILE program A no
Diagonalisation Idea
• … is very clever
• … needs items of interest to be enumerable
• … was discovered by Cantor in 1891 to show the existence of sets that are larger than the set of natural numbers.
Georg Cantor 1845-1918
19
END
© 2008-21. Bernhard Reus, University of Sussex
Next time:
More on semi-decidability
20