Pre se nta zio ne
Gli arg om en tit rat tat i
Ricordiamo alcune nozioni di base
Introduzione alla calcolabità
ma cch ine di T urin g
dec idib ilità
ling uag gi
ese mp i di pro ble mi d ecid ibili
Argomenti avanzati
pro ble mi i nde cidib ili
ridu zion e
teo rem a d i Ric e
min im un des crip tion len gth
ind ecid ibilit àd ella log ica del prim o o rdin e
3
Gli arg om en tit rat tat i
Introduzione alla complessità
defi nizio ne d i P, NP, coP , co NP
ese mp i di pro ble mi i n q ues te c lass i
ridu zion e e NP -co mp lete zza
Argomenti avanzati
teo rem a d i Co ok-L evin
rela zion i fra P, N P, N P-c om ple tie i lo ro c om ple me nti
isom orfis mo , lin gua ggi spa rsi
com ple ssità spa ziale
alg oritm i pro bab ilisti ci
qua ntu m c om puti ng
4
Ob bie ttivo L’ob bie ttiv o d el c orso è
rive dere in m anie ra form ale i con cett i su calc ola bilit à e com ple ssità già vist i du ran te il co rso di l aure a
intr odu rre alcu ni a rgo me nti a van zati Si tr atta di a rgo me nti m ate ma tici (de finiz ion i e t eore mi) … per ren derl i m eno no iosi e p er r icor darl i m eglio
cerc here mo di d im ostr are ins iem e a lcun i ris ulta ti
ved rem o n um ero si e sem pi
Es am e L’es am e co nsis te in
sce glie re un arg om ento o u n pro ble ma co nne sso co n gli arg om enti de l co rso
app rofo ndir lo cerc and o e stu dia ndo la le tter atu ra com e s e s dov ess e sc rive re u na r evie w
scriv ere un a p icco lo doc um ento (5 -10 pa gin e) che ria ssu me qua nto ap pre sso
lo s tile do vre bbe ess ere qu ello di u na r evie w che no n si lim ad elen care so lo i rif erim enti m a c erc hi di rias sum erli spie garl i (a d ese mp io, com e se ste sse pr epa ran do delle disp ens e p er g li st ude nti d el d otto rato … .)
Es am e
Esempi di argomenti per l’esame
minimum descriptionlengthe machinelearning
quantum computing
algoritmi di fattorizzazioneintera
algoritmi per il graphmatching
…
7
Li bri
Libroprincipale
M. Sipser, “Introduction to theory of computation”,2°edition, ThompsonAltririferimenti
C. Papadimitriou, “Computational complexity”,Addison Wesley
C. Toffalori, F. Corradini, S. Leonesi, S. Mancini, “Teoriadellacomputabilitàe complessità”, McGraw-Hill
8
In tro du cto ry no tio ns
Ca lcu lab ility
Computational calculabitytheory
the investigation of the problems that can be solved using reasonable computers
the reasonable computers are those …that can be constructed (now or in the future)
Co m ple xity
Computational complexity theory
theinvestigation of thetime, memory,or other resources requiredforsolving computationalproblems
the resources are usually measured as a function of ofthe input dimension
11
Big O -N ota tio n
It will be extremely convenient to use the following‘order-notation’to express our complexities.Definition: Let f and g be two functions N→R +.We say and write f(n) = O(g(n)) if and only if thereare two positive constant c and n0 such thatf(n) ≤cg(n) for all n≥n0 .“g (n ) is an (a sym pto tic ) u pp er bo un d o n f (n )”.
12
Li ttle o- No tat ion
D e fin iti o n : L e t f a n d g b e tw o fu n c tio n s N → R
+. W e s a y a n d w rit e f( n ) = o (g (n )) if a n d o n ly
0 )n (g )n (f lim
n=
∞→• b ig -O is a b o u t “ le s s -o r- e q u a l-t h a n ”, • lit tle o is a b o u t “ s tr ic tly le s s th a n ”.
La ng ua ge s
Given an alphabet Σ, we can make a word or stringby concatenating the letters of Σ.
A language L is a set of words, i.e.
L⊆Σ*, where * is the kleeneoperator
Examples
Σ={0,1,.}, the set of decimal binary numbers
Σ={a,b,c,d,e,f,…}, the set of italianwords
Ac ce pte d La ng ua ge s
Let L be a language ⊆S
a machine M acceptL if
M x ∈∈∈∈ S “ a c c e p t”
“ re je c t” if a n d o n ly if x ∉ if a n d o n ly if x ∈
15
Re gu lar la ng ua ge s
Given an alphabet Σ, any expression that can be obtainedby
1.R = a, with a∈Σ(a symbol of the alphabet)
2.R =ε(the null string)
3.R =∅(the void expression)
4.R = (R1 | R2 ), the alternation
5.R = (R1 R2 ), the concatenation
6.R = (R1 *), the kleeneclosure
A language is regular if it can be defined by a regular expression
16
Re gu lar la ng ua ge s: e xa m ple s
Bin ary po sitiv e n um bers (1 | 0) *
A d ecim al n um ber with on e in teg er d igit and tw o d ecim al d igits (+ |-|
ε)(0 |1|2 |… |9)* . (0 |1|2 |… |9) (0|1 |2|… |9)
ide ntifi ers of a pro gra mm ing lan gua ge (a|b |c| … |z|) (a| b|c | … |z|0 |1| …|9 |)*
Fi nit e A uto m ato n a nd reg ula r la ng ua ge s
Alternative definitionA language is regular if and only if it can be accepted byfinite automaton
A finite (state) automataa simple machine that reads a singleinput character at every time stephas an internal state that can assumea finite number of different valuesinternal state are of two different types(accept, reject) that define whetherthe read string is accepted or not E132.1 FA(internal state)
Fi nit e A uto m ato n a nd reg ula r la ng ua ge s
FormallyA nondeterministic finite automaton (FA) M is defined bytuple M=(Q,Σ,δ,q0 ,F), with Q: finite set of statesΣ: finite alphabetδ: transition functionδ:Q×Σε →P (Q)q0 ∈Q: start stateF⊆Q: set of accepting states
The automata is called deterministic or non determinaccording whether δ(q,a) is a singleton or not for eac
19
Fi nit e a uto m ato n
q
1q
2q
31 0
0 ,1 0 1 s ta te s tr a n s iti o n r u le s
s ta rti n g s ta te
a c c e p tin g s ta te The de term inis tic a uto ma ton tha t re cog nize s th e la ngu age : 0*1 ( (1 |0) (0|1 ))*
20
So m e p rop ert ies of FA an d r eg ula r lan gu ag es
Det erm inis tic FA (DF A) and no n dete rm inis tic FA (NF A) are equ ivale nt:
the y a cce pt a ll a nd o nly all t he r egu lar l ang uag es
the re e xist alg orith ms to t ran sfo rm a D FA into an eq uiva len t FA, and vic e v ersa …
FA a nd r egu lar e xpre ssio n a re e quiv alen t
the re exis t a lgo rith ms to tran sfo rm a FA to the eq uiva len t reg ula r ex pre ssio n a nd, vice ve rsa ,…
Reg ula r lan gua ges are clos ed und er unio n, inte rse ctio n, com ple me nta tion , co nca ten atio n
the re e xist alg orith ms to t ran sfo rm a F A to an oth er F A th at acc epts the co mp lem ent lan gua ge
Co nte xt fre e la ng ua ge s Def initi on A c onte xt fr ee g ram ma r G =(V ,
Σ,R,S ) is defi ned by
V: a fin ite s et v aria ble s
Σ
: fin ite s et t erm ina ls (w ith V
∩Σ=
∅)
R: f inite set of s ubs titu tion rule s V
→(V
∪Σ)*
S: s tart sym bol
∈V
Def initi on The lan gua ge of g ram ma r G , de note d b y L (G) , is the set of strin gs of term ina l sy mb ols tha t c an be obta ine d b y app lyin g th e su bstit utio n ru les from the sta rt s ym bol
L(G ) = { w
∈Σ* | S
⇒* w
}Ex am ple : th e b oo lea n alg eb ra
G=(V,Σ,R,S) withV = {S,Z}Σ= {0,1,(,),¬,∨,∧}R: S→0S →¬(S) S →(S)∨(S) S →(S)∧(S)
Some elements of L(G):0¬((¬(0))∨(1))(1)∨((0)∧(0))
23
Pa rse T ree s
The parse tree for (0)∨((0)∧(1))
S→0 | 1 | ¬(S) | (S)∨(S) | (S)∧(S) S
()∨)(SS
()∨)( SS 0
01
24
Ex am ple : a s im ple pr og ram m ing la ng ua ge
G=(V,Σ,R,S) withV = {S,C,E,B}Σ= {id,val,=,(,),if,then,==}R: S→C;S | εC→id=EC→if (B) then S endE→id|valB→E==E A program in L(G):
id=val;id=id;if (id==val) thenid=valend
Pu sh do w n a uto m ata A p ush dow n a uto ma ta
is a m ach ine co mp ose d b y
a fin ite s tate co ntro l un it
a st ack tha t co nta in s ym bols
it c an rea d o ne inp ut cha ract er at eac h st ep
it can add , rea d and rem ove sym bols fro m t he s tack Pus hdo wn au tom ata ca n re cog nize (de cide ) co nte xt fr ee l ang uag es ) ) 0 ( ( ) 0 (
PDA(internal state)M ore ab ou t c on tex t fr ee la ng ua ge s
A context free language
can be de cide d b y a pa rse rs ( auto ma ta t hat use a s tack )
can be de cide d in O(n
3) (O( n
2) if th e la ngu age is not am big uou s)
Contextfree languages strictly contains regularlanguages
for exa mp le, the la ngu age {a
nb
n|n> 0} is con tex t free lan gua ges , bu t no t a r egu lar l ang uag e
27
M ore la ng ua ge s Con tex t-se nsit ive gra mm ars
the rule s ar e in the for m
α
Aβ
→αγβ
wh ere A is a no n te rm ina l an d α
,β,γ are str ing s o f te rm ina ls and no n te rm ina ls, γ can not be n ull
the rule S
→εis a llow ed i f
Sdoe s n ot a ppe ar o n th e rig ht s ide of any rule
no alg orith m is kn ow n to de cide Co nte xt-s ens itive lan gua ges in poly nom ial t im e Unr estr icte d g ram ma rs
the rule s ar e a ny f orm
no alg orith m is kno wn to d ecid e lan gua ges g ene rate d by unr estr icte d g ram ma rs
28
Ch om sky lan gu ag e g era rch y
All inclusions are strict!!
regular contextfree contextsensitive generatedbyno restrictiongrammar Allthe languages
Tu rin g Tu rin g m ach ine s m ach ine s
Tu rin g M ach ine s
Alan M. Turing (1912–1954)
In1936, Turingintroducedhis abstract model computation in his article “On Computable Numbers, wan application to the Entscheidungsproblem”.
At the same time, Alonzo Church published similar ideand results.
TheTuringmodel has becomethestandardmodtheoretical computer science.
31
In for m al D esc rip tio n T M
Depending on its state and the letter xi , the TM-writes down a letter, -moves its read/write head left or right, and-jumps to a new state.
in te rn a l s ta te s e t Q R L
L__1#0_1101 At every step, the head of theTM M reads aletter xi from theone-way infinitetape.32
In pu t C on ve ntio n
s ta te q
0 LL___wwwn21Initially, the tape contains the inputw∈Σ*, padded with blanks “_”,and the TM is in start state q0 .
During the computation, the head moves leftand right (but not beyond the leftmost point),the internal state of the machine changes,and the content of the tape is rewritten.
Ou tpu t C on ve ntio n
The computation can proceed indefinitely, or themachines reaches one of the two halting states:
s ta te q
accept LL_vvvm21s ta te q
reject L_vvvm21o r
Tu rin g M ach ine (D ef. 3.3 )
A T u rin g m a c h in e M is d e fin e d b y a 7 -tu p le ( Q , Σ , Γ , δ ,q
0,q
accept,q
reject), w ith •
Q finite set of states•Σfinite input alphabet (without “_”)•Γfinite tape alphabet with { _ }∪Σ⊆Γ•q0 start state∈Q•qaccept accept state∈Q•qreject reject state∈Q• δ th e tr a n s iti o n fu n c tio n δ : Q \{ q
accept,q
reject} × Γ → Q × Γ × {L ,R }
35
Co nfig ura tio n o f a T M
The configuration of a Turing machine consists of•the current state q∈Q•the current tape contents ∈Γ*•the current head location∈{0,1,2,…}
This can be expressed as an element of Γ*×Q×Γ*:
L__1#0_1101
q9 becomes “101 q9 1_0#1”
36
An Ele m en tar y TM St ep
Let u,v∈Γ* ; a,b,c∈Γ; qi ,qj ∈Q, and M a TM withtransition functionδ.
We say that the configuration “uaqi bv”yieldstheconfiguration “uacqj b”if and only if:δ(qi ,b) = (qj ,c,R).
Similarly, “uaqi bv”yields “u qj acb”if and only ifδ(qi ,b) = (qj ,c,L).
Sta te dia gra m s o f T M s
L ik e w ith P D A , w e c a n r e p re s e n t T u rin g m a c h in b y ( e la b o ra te ) d ia g ra m s .
If tr a n s iti o n r u le s a y s : δ (q
i,b ) = ( q
j,c ,R ), th e n :
q
iq
jb → c ,R
Te rm ino log y
starting configurationon input w: “q0 w” accepting configuration: “uqaccept v”
rejecting configuration: “uqreject v”
The accepting and rejecting configurations arethe halting configurations.
39
Ex am ple : A = { 0
j| j= 2
n}
Approach: If j=0 then “reject”; If j=1 then “accept”; if j is even then divide by two; if j is odd and >1then “reject”. Repeat if necessary.
1.Check if j=0 or j=1, accept/reject accordingly2.Check, by going left to right if the string haseven or odd number of zeros3.If odd then “reject”4.If even then go back left, erasing half the zeros5.goto1 Goal:To build a TM that accepts all and only the strings in
A = { 0
j| j = 2
n}
40
Ac ce ptin g T M s
A Turing machine M acceptsinput w∈Σ*if and only if there is a finite sequence of configurations C1 ,C2 ,…,Ck with
•C1 the starting configuration “q0 w”•for all i=1,…,k–1 Ci yields Ci+1 (following M’s δ)•Ck is an accepting configuration “uqaccept v”
The language that consists of all inputs that areaccepted by M is denoted by L(M).
Tu rin g r eco gn iza ble
A language L is Turing-recognizableif and onlyif there is a TM M such that L=L(M).
Note: On an input w∉L, the machine M canhalt in a rejecting state, or it can ‘loop’indefinitely.
H o w d o y o u d is tin g u is h b et w ee n a v er y lo n g co m p u ta tio n a n d o n e th at w ill n ev er h al t?
Also called: arecursively enumerablelanguage.43
En um era tin g La ng ua ge s
When a TM E generates the words of a language,E is an enumerator (cf. “recursively enumerable”).
A Turing machine E enumeratesthe language Lif it prints an (infinite) list of strings on the tapesuch that all elements of L will appear on the tape,and all strings on the tape are elements of L.(E starts on an empty input tape. The strings can appear in any order; repetition is allowed.)
44
En um era tin g = R eco gn izin g
Theorem: A language L is TM-recognizableif and only if L is enumerable.
Proof: (“if”) Take the enumerator E and input w.Run E and check the strings it generates.If w is produced, then “accept”and stop,otherwise let E continue.(“only if”) Take the recognizer M.Let s1 ,s2 ,…be a listing of all strings ∈Σ*⊇L. For j=1,2,…run M on s1 ,…,sj for j time-steps.If M accepts an s, print s. Keep increasing j.
Tu rin g D ecid ab le ( De f. 3 .5)
Also called: a recursivelanguage. A language L=L(M) is decidedby the TM M if onevery w, the TM finishes in a halting configuration.(That is: qaccept for w∈L and qreject for all w∉L.)
A language L is Turing-decidableif and onlyif there is a TM M that decides L.
M ult ita pe Tu rin g M ach ine s
A k-tape Turing machine M has k differenttapes and read/write heads. It is thus defined
by the 7-tuple (Q,Σ,Γ,δ,q0 ,qaccept ,qreject ), with
•Q finite set of states
•Σfinite input alphabet (without “_”)
•Γfinite tape alphabet with { _ }∪Σ⊆Γ
•q0start state∈Q
•qacceptaccept state∈Q
•qreject reject state∈Q
•δthe transition functionδ: Q\{qaccept ,qreject }
×
Γ k→Q×
Γ k×{L,R} k47
k- tap e T M s ve rsu s 1 -ta pe T M s
Theorem: For every multi-tape TM M, thereis a single-tape TM M’such that L(M)=L(M’).Or, for every multi-tape TM M, there is anequivalentsingle-tape TM M’.
Proving and understanding these kinds of robustnessresults, is essential for appreciating the power of theTuring machine model.
From this theorem follows:A language L is TM-recognizable if and only ifsome multi-tape TM recognizes L.
48
Pro of ske tch
L e t M = (Q , Σ , Γ , δ ,q
0,q
accept,q
reject) b e a k -ta p e T M . C o n s tr u c t 1 -ta p e M ’ w ith e x p a n d e d Γ ’ = Γ∪ Γ∪ {# } R e p re s e n t M -c o n fig u ra tio n u
1q
ja
1v
1, u
2q
ja
2v
2, … , u
kq
ja
kv
kb y M ’ c o n fig u ra tio n
,q
j# u
1a
1v
1# u
2a
2v
2# … # u
ka
kv
k(T h e ta p e s a re s e p e ra te d b y # , t h e h e a d p o s iti o n s a re m a rk e d b y u n d e rli n e d le tte rs .)
Pro of ske tch
O n in p u t w = w
1… w
n, t h e T M M ’ d o e s th e fo llo w in • P re p a re in iti a l s tr in g : # w
1…w
n# _ # L # _ # _ L • R e a d th e u n d e rli n e d in p u t l e tte rs ∈ Γ
k• S im u la te M b y u p d a tin g th e in p u t a n d th e u n d e rli n in g o f t h e h e a d -p o s iti o n s . • R e p e a t 2 -3 u n til M h a s r e a c h e d a h a lti n g s ta • H a lt a c c o rd in g ly .
P S : I f t h e u p d a te r e q u ire s o v e rw rit in g a # s y m b th e n s h ift th e p a rt # L _ o n e p o s iti o n to th e r ig h
No nd ete rm inis tic T M s
A nondeterministic Turing machineM can have
several options at every step. It is defined bythe 7-tuple (Q,Σ,Γ,δ,q0 ,qaccept ,qreject ), with
•Q finite set of states
•Σfinite input alphabet (without “_”)
•Γfinite tape alphabet with { _ }∪Σ⊆Γ
•q0 start state∈Q
•qacceptaccept state∈Q
•qrejectreject state∈Q•δthe transition functionδ: Q\{qaccept ,qreject }
×
Γ→P
(Q×
Γ×
{L,R})51
Co m pu tin g w ith N on de ter m inis tic T M s
C1
C6 C5 C4C3 C2 Evolution of the n.d. TMrepresented by a treeof configurations (ratherthan a single path).
M “reject”
“accept” If there is (at least)one accepting leave,then the TM accepts. t=1
t=2
t=3
52
Sim ula tin g N on de ter m inis tic T M s w ith D ete rm inis tic O ne s
We want to search every path down the treefor accepting configurations.
Bad idea: “depth first”. This approach can getlost in never-halting paths.
Good idea: “breadth first”. For time step 1,2,…we list all possible configurations of the non-deterministic TM. The simulating TM accepts when it lists an accepting configuration.
Bre ad th Fi rst
Let b be the maximum numberof children of a node. C1
C6 C5 C4C3 C2
M “reject”
“accept” t=
Any node in the tree canbe uniquely identified bya string∈{1,…,b}*.
Example: location of therejecting configuration is (3,1).
With the lexicographical listingε, (1), (2),…, (b), (1,1),(1,2),…,(1,b), (2,1),…et cetera, we cover all nodes.
Pro of of Th eo rem (s im ula tin g N TM )
Let M be the nondeterministic TM on input w.
The simulating TM uses three tapes:T1 contains the input wT2 the tape content of M on w at a nodeT3 describes a node in the tree of M on w.
1)T1 contains w, T2 and T3 are empty2)Simulate M on w via the deterministic pathto the node of tape 3. If the node accepts,“accept”, otherwise go to 3)3)Increase the node value on T3; go to 2)
55
Ro bu stn ess
Just like k-tape TMs, nondeterministic Turingmachines are not more powerful than simple TMs:
Every nondeterministic TM has an equivalent 3-tape Turing machine, which –in turn–has anequivalent 1-tape Turing machine.
Hence: “A language L is recognizable if and onlyif some nondeterministic TM recognizes it.”
T h e T u rin g m ac h in e m o d el is e x tr em el y r o b u st .
56
Oth er Co m pu tat ion al M od els
W e c a n c o n s id e r m a n y o th e r ‘ re a s o n a b le ’ m o d e ls o f c o m p u ta tio n : n e u ra l n e tw o rk s , q u a n tu m c o m p u tin g …
E x p e rie n c e te a c h e s u s th a t e v e ry s u c h m o d e l c a n b e s im u la te d b y a T u rin g m a c h in e .
C h u rc h -T u rin g T h e s is :
T h e in tu iti ve n o tio n o f c o m p u tin g a n d a lg o ri th m s is c a p tu re d b y th e T u ri n g m a ch in e m o d el .
Ra nd om Ac ce ss M ach ine s RA M M ach ine s
A se t of R
1, R
2, R
3, … of r egis ters isa vaila ble
Eve ry reg iste ris a m em ory tha tca n co nta in a p osit ive inte ger
Pro gra m c onta ins a se que nce of in stru ctio ns in
Increment: Ri ++The registrerisincreasedby1
Decrement: Ri --The registeri decreasedb1. Iftheregisterisalready0, the instructionhasno effect
conditionaljump: IF RiGOTO L1Ifthe registerisnotnull, wejumpat L1 IF R1 GOTO ciclociclo:R2++R1 --IF R1 GOTO ciclofine: The sumof the tworegistR1e R2
No n-d ete rm inis tic RA M
In non -de term inis tic RA M, thre e oth er inst ruc tion sar e a vaila ble
ran dom cho ice: FO RK tak es in inp ut tw o inst ruc tion s and exe cute one of t hem
ACC EPT the m ach ine acc epts
REJ ECT the m ach ine reje cts
An inp ut is acc ept, if the re is a p ath tha t allo ws the pro gra m t oa cce pt.
aIF R1GOTO bR1--FORK{GOTO a,R2++ }GOTO aDIVIF R3 GOTO reACCEPTreREJECT Isnumberin R1prime ?Weusea procedure DIV thatwhetherR2isa factorof59
µ -re cu rsive fu nc tio ns
µ
-rec ursi ve f unc tion s ar e d efin ed a s
bas ic fu nctio ns
con sta nts, f( x
1,..,x
k)= n
incr em ent, S (x)= x+ 1
pro ject ion , U
s(x
1,..,x
k)= x
scom pos ed f unc tion s: if h , g
i, ar e
µ-rec ursi ve f unc tion s th en f is
µ-rec ursi ve
com pos itio n, f( x
1,..,x
k)= h(g
1(x
1,..,x
k),… , g
r(x
1,..,x
k))
recu rsio n, f( 0,x
1,..,x
k)= g(x
1,..,x
k) f(y+ 1,x
1,..,x
k)= h(y ,f(y ,x
1,..,x
k), x
1,..,x
k)
60
µ -re cu rsive fu nc tio ns : m ult ipli ca tio n
piu(0,b)=b piu(a+1,b)=piu(a,b)+1
per(0,b)=0per(a+1,b)=piu(per(a,b),b) base recursion: g is the projection operator constants, f(x1,..,xk)=n
increment, S(x)=x+1
projection, U s(x1,..,xk)=xs
composition, f(x1,..,xk)=h(g1(x1,..,xk),…, gr(x1,..,xk))
recursion, f(0,x1,..,xk)= g(x1,..,xk)f(y+1,x1,..,xk)=h(y,f(y,x1,..,xk), x1,..,xk)
recursion: h is the successor
base recursion: g is a constantrecursion: h is the compositionof piuand the projection
Un ive rsa l p rog ram m ing la ng ua ge s A u nive rsa l pro gra mm ing lan gua ge ( for a R AM m ach ine ) m ust inclu de a t le
incr em ent and de cre me nt o pera tors
inst ruc tion co nca ten atio n a nd
GO TO an d IF or
recu rsio n o r
WH ILE or
und efin ed F OR Rem ark
A F OR is defi ned if the va lue s a ssig ned to th e F OR va riab le a re d efin befo re s tart ing the ex ecu tion of t he F OR
f.i. f or(i= 0;i< 10;i ++ )
a d efin ed F OR is n ot s uffic ien t to ob tain an un iver sal ma chin e. W hy?
De cid ibil ity De cid ibil ity
63
Hi lbe rt’s 10 th Pr ob lem
In 1900, David Hilbert (1862–1943) proposed
his Mathematical Problems (23 of them).
The Hilbert’s 10th problem is:Determination of the
solvability of a Diophantine equation.
Given a Diophantine equation with any number of
unknown quantities and with rational integral numerical
coefficients: To devise a process according to which it
can be determined by a finite number of operations
whether the equation is solvable in rational integers.
64
Dio ph an tin e E qu atio ns
Let P(x1 ,…,xk ) be a polynomial in k variableswith integral coefficients. Does P have anintegral root (x1 ,…,xk )∈Z k?
Example: P(x,y,z) = 6x 3yz + 3xy 2–x 3–10has integral root (x,y,z) = (5,3,0).
Other example: P(x,y) = 21x 2–81xy+1does not have an integral root.
(Un )so lvi ng Hi lbe rt’s 10 th
Hilbert’s “…a process according to which it canbe determined by a finite number of operations…”needed to be defined in a proper way.
This was done in 1936 by Church and Turing.
Matijasevičproved that Hilbert’s 10th problemis unsolvable in 1970.
De cid ab ility
Thus, we are now ready to tackle the question:
W h ic h la n g u a g es a re T M -d ec id a b le , T u ri n g - re co g n iz a b le , o r n ei th er ? W h a t c a n c o m p u te rs d o a n d w h a t n o t?
We do this by considering the question:
Assuming the Church-Turing thesis, these arefundamental properties of the languages.
67
De scr ibin g T M Pr og ram s
Three Levels of Describing algorithms:
•formal (state diagrams, CFGs, et cetera)
•implementation (pseudo-Pascal)
•high-level (coherent and clear English)
Describing input/output format:
TMs allow only strings ∈Σ* as input/output.If our X and Y are of another form (graph, Turing
machine, polynomial), then we use<X,Y>to
denote ‘some kind of encoding∈Σ*’.
68
De cid ing R eg ula r La ng ua ge s
The acceptance problemfor deterministicfinite automata is defined by:ADFA = {<B,w>| B is a DFA that accepts w }
Note that this language deals with all possibleDFAsand inputs w, not a specific instance.
Of course, ADFA is a TM-decidable language.
A
DFAis D ecid ab le
Proof: Let the input <B,w>be a DFA with
B=(Q, Σ, δ, qstart , F) and w∈Σ*.
The TM performs the following steps:
1)Check if B and w are ‘correct’, if not: “reject”
2)Simulate B on w with the help of two pointers:
Pq ∈Q for the internal state of the DFA, and Pw ∈{0,1,…,|w|} for the position on the string. While we increase Pw from 0 to |w|, we change Pq according to the input letter wPwand the transition function valueδ(Pq ,wPw ).
3)If M accepts w: “accept”; otherwise “reject”
Re gu lar Ex pre ssio ns
The acceptance problemAREX = {<R,w>| R is a regular expressionthat can generate w }is a Turing-decidable language.
Proof Theorem.On input <R,w>:1.Check if R is a proper regular expressionand w a proper string2.Convert R into a DFA B3.Run earlier TM for ADFA on<B,w>
71
Em ptin ess T est ing
Another problem relating to DFAsis theemptiness problem:EDFA = {<A>| A is a DFA with L(A) =∅}
How to decide this language?
This language concerns the behavior of theDFA A on all possible strings.
Less obvious than the previous examples.
72
Pro of for D FA -E m ptin ess
Algorithm for EDFA on input A=(Q,Σ,δ,qstart ,F):
1)If A is not proper DFA: “reject”
2)Make set S with initially S={qstart }
3)Repeat |Q| times:
a)If S has an element in F then “reject”
b)Otherwise, add to S the elements that
can beδ-reached from S via:“If∃qi ∈Sand∃s∈Σwithδ(qi ,s)=qj , then qj goes into Snew ”
4)If final S∩F =∅“accept”
DFA -E qu iva len ce
A problem that deals with two DFAs:EQDFA = {<A,B>| L(A) = L(B) } Theorem: EQDFA is TM-decidable.
Proof: Look at the symmetric differencebetweenthe two languages:
Note: “L(A)=L(B)”is equivalent with an empty
symmetric difference between L(A) and L(B).
This difference is expressed by standard DFAtransformations: union, intersection, complement. ))B(L)A(L())B(L)A(L(∩∪∩
Pro of of Th eo rem (c on t.)
Algorithm on given<<<<A,B>>>>:
1)If A or B are not correct DFA: “reject”
2)Construct a third DFA C that accepts thelanguage
3)Decide with the TM of the previous theorem
whether or not C∈EDFA4)If C∈EDFA then “accept”;If C∉EDFA then “reject”
))B (L )A (L ( ))B (L )A (L ( ∩ ∪ ∩
75
Co nte xt- Fr ee La ng ua ge s
Similar languages for context-free grammars:
ACFG = {<G,w>| G is a CFG that generates w } EQCFG = {<G,H>| G and H are CFGswith L(G)=L(H) } ECFG = {<G>| G is a CFG with L(G)=∅}
The problem with CFGsand PDAsis that theyare inherently nondeterministic.
76
Ch om sky No rm al Fo rm
DefinitionA context-free grammar G = (V,Σ,R,S) is in Chomskynormal formif every rule is of the formA→BC or A→xwith variables A∈V and B,C∈V \{S}, and x∈Σ. For the start variable S we also allow “S→ε”
The derivation S⇒* w requires 2|w|–1 steps(apart from S⇒ε). Every context-free grammar can be transformed into anequivalent Chomsky NF grammar.
De cid ing C FG s (1 )
Theorem:The languageACFG = {<G,w>| G is a CFG that generates w }is TM-decidable.
Proof:Perform the following algorithm:1)Check if G and w are correct, if not “reject”2)Rewrite G to G’in Chomsky normal form3)Take care of w=εcase via S→εcheck for G’4)List all G’derivations of length 2|w|–15)Check if w occurs in this list; if so “accept”; if not “reject”
De cid ing C FG s (2 )
Theorem:The languageECFG = {<G>| G is a CFG with L(G)=∅}is TM-decidable.
Proof:Perform the following algorithm:1)Check if G is proper, if not “reject”2)Let G=(V,Σ,R,S), define set T=Σ3)Repeat |V| times:•Check all rules B→X1 …Xk in R•If B∉T and each X1 …Xk is in T then add B to4)If S∈T then “reject”, otherwise “accept”
79
Eq ua lity CF Gs
EQCFG = {<G,H>| G and H are CFGswith L(G)=L(H) }?
For DFAswe could use the emptiness decisionprocedure to solve the equality problem. What about the equality language
For CFGsthis is not possible…(why?)…because CFGsare not closed under complementation or intersection.
Later we will see that EQCFG is not TM-decidable.
80
De cid ing La ng ua ge s
W e n o w k n o w th a t t h e la n g u a g e s :
A
CFG= { < G ,w > | G is a C F G th a t g e n e ra te s w } A
DFA= { < B ,w > | B is a D F A th a t a c c e p ts w }
a re T M d e c id a b le .
W h a t a b o u t t h e o b v io u s n e x t c a n d id a te A
TM= { < M ,w > | M is a T M th a t a c c e p ts w } ?
Is o n e T M c a p a b le o f s im u la tin g a ll o th e r T M s ?
Th e Un ive rsa l T M
Given a description<M,w>of a TM M andinput w, can we simulate M on w?
We can do so via a universal TMU (2-tape):1)Check if M is a proper TMLet M = (Q,Σ,Γ,δ,q0,qaccept,qreject)2)Write down the starting configuration<q0w>on the second tape3)Repeat until halting configuration is reached:•Replace configuration on tape 2 by nextconfiguration according toδ4)“Accept”if qaccept is reached; “reject”if qreject
Th e Ha ltin g P rob lem
The existence of the universal TM U shows that ATM = {<M,w>| M is a TM that accepts w }is TM-recognizable, but can we also decideit?
The problem lies with the cases when M doesnot halt on w. In short: the halting problem.
We will see that this is an insurmountableproblem: in general one cannot decide if a TMwill halt on w or not, hence ATM is undecidable.
83
Are th ere un de cid ab le lan gu ag es?
For Σ={0,1}, there are 2 kwords of length k.
A language is a set words: there are languages L⊆Σ k.
A TM M an be described by a string: there are 2 k TMs of length k.
An ideaLet us count languages and TMs, if TMsare less than languages then weknow that some language cannot be computed!!
However, languages and TMsare infinite and we need a more sophisticateway to compare them )2( k2
84
Ca rd ina lity
A set S has k elements if and only if there isa bijectionpossible between S and {1,2,…,k}.
S and {1,…,k} have the same cardinality.
If there is a surjection possible from {1,…,n} to S, then n≥|S|.
We can generalize this way of comparing thesizes of sets to infinite ones.
Co un tab le S ets
If there exists a surjectivefunction F:N→Sthe set S may not be infinite“The set S has not more elements than N.” If there exists a surjectivefunction F:S→N, the set S is infinite“The set N has not more elements than S.”
If there exists a bijectivefunction F:N→S.The set S is countable“The sets N and S are of equal size.”
So m e C ou nta ble In fin ite Se ts
bbbaabaaba aaaaaaaaaaaaaaaaaaaaa )3,0()0,2()1,1()2,0()0,1()1,0()0,0( 3322110 6543210
ε ε −+−+−+
O n e c a n m a k e b ije c tio n s b e tw e e n N a n d Z , N
2, { a }* , { a ,b }* :
87
A B ig C ou nta ble Se t
Consider the set N*, the set of finite sequencesof numbers: (0)∈N*, (4,63)∈N*, (1,0,…,1)∈N*.
This set is also countable infinite.
How do make the bijectionbetween N* and N?
1.There are infinitely many primes
p1 =2, p2 =3, p3 =5, … 2.Every number n∈{2,3,…}has a unique primefactorization: 84 = p1 ·p1 ·p2 ·p4
88
Bije ctio n be tw ee n N an d N *
Let (n1 ,n2 ,…,nk )∈N* Consider the number 1nk 1n2 1n1 k21
p p p m
+++⋅ = L
Infinitely many primes: For every k this is possible.
The “+1”enables us to make a distinctionbetween (1,4,0) and (1,4). Unique prime factorization: Given m, we candetermine (n1 ,n2 ,…nk )
Un co un tab le S ets
There are infinite sized sets that are not countable.Typical examples areℜ,
P
(N) andP
({0,1}*)We prove this by a diagonalizationargument.In short, if S is countable, then you can make alist s1 ,s2 ,…of all elements of S.Diagonalizationshows that given such a list,there will always be an element x of S thatdoes not occur in s1 ,s2 ,…
Un co un tab ility of P ( N )
The set
P
(N) contains all the subsets of {0,1,2,…}.There is a bijectionbetween P (N) and{0,1}∞(the set of infinite bit string).Each subset X⊆Ncan be identified by an infinitestring of bits x0 x1 x2 ... such that xj =1 iffj∈X.
Proof by contradiction: Assume
P
(N) is countableHence there must exist a bijectionF:N→{0,1} ∞. “There is a list of allinfinite bit strings.”
91
Dia go na liza tio n
Try to list all possible infinite bit strings:
O M L L L L
0 1 0 1 0 3 0 0 0 0 1 2 1 1 1 1 1 1 0 0 0 0 0 0
Look at the bit string on the diagonal ofthis table: 0101…The negation of thisstring (“1010…”) does not appear in the table.
92
No bij ect ion N → {0 ,1}
∞Let F be a functionN→{0,1} ∞.F(0),F(1),F(2),…are all infinite bit strings.
Define the infinite string Y=Y0 Y1 Y2 …byYj =NOT(j-thbit of F(j)) On the one hand Y∈{0,1} ∞, but on the other hand: for every j∈Nwe know that F(j)≠Ybecause F(j) and Y differ in the j-thbit.
F cannot be a surjection: {0,1} ∞is uncountable.
Un co un tab ility
W e ju s t s h o w e d th a t t h e re it is im p o s s ib le to h a v e s u rje c tio n fr o m N to th e s e t { 0 ,1 }
∞.
S im ila r p ro o fs a re p o s s ib le fo r t h e u n c o u n ta b ilit y o f t h e s e ts ℜ , P ({ 0 ,1 }* ), … .
Co un tin g T M s
Observation: Every TM has a finite description;there is only a countable number of different TMs.(A description<M>can consist of a finite stringof bits, and the set {0,1}* is countable.)
Our definition of Turing recognizable languagesis a mapping between the set of TMs {M1 ,M2 ,…}and the set of languages {L(M1 ),L(M2 ),…}⊆
P
(Σ*).Question: How many languages are there?
95
Co un tin g La ng ua ge s
There are uncountable many different languagesover the alphabet ΣΣΣΣ={0,1}: the set of languages isP ({0,1}*)With the lexicographical orderingε,0,1,00,01,…of Σ*,every L coincides with an infinite bit string via its characteristic sequenceχL .Example for L={0,00,01,000,001,…} withχL = 0101100…
L L L
1110011010 XXXXXXL 0100010001110010010*
L χ εΣ
96
Co un tin g T M s a nd La ng ua ge s
There is a bijectionbetween the set of languages
over the alphabet Σ={0,1} and the uncountable
set of infinite bit strings {0,1} ∞.There are uncountable many differentlanguages L⊆{0,1}*.Hence there is no surjection possible from the
countable set of TMs to the set of languages.
Specifically, the mapping L(M) is not surjective.
Conclusion: There are languages that are not
Turing-recognizable. (A lot of them.)
Is T his R ea lly In ter est ing ?
We now know that there are languages thatare not Turing recognizable, but we do not know what kind of languages are non-TMrecognizable.
Are there interesting languages for whichwe can prove that there is no Turingmachine that recognizes it?
Pro vi ng Un de cid ab ility (1 )
Consider –again–the acceptance languageATM = {<M,w>| M is a TM that accepts w }. Proof that ATM is not TM-decidable(Contradiction) Assume that TM G decides ATM :
does if M reject"" not accept w = w, M G w accepts M if accept""
From G we construct a new TM D that will getus into trouble…
99
Pro vi ng Un de cid ab ility (2 )
The TM D works as follows on input <M>(a TM):1)Run G on<M,<M>>2)Disagree with the answer of G(The TM D always halts because G always halts.)
=MM, accepts G if reject"" MM, rejects G if accept""MD
In s h o rt:
=Maccept does M if reject"" Maccept not does M if accept""MD
H e n c e :
Now run D on<D>(“on itself”)…
100
Pro vi ng Un de cid ab ility (3 )
= D accept does D if reject"" D accept not does D if accept"" D D
Result:This does not make sense: D only acceptsif it rejects, and vice versa. (Note again that D always halts.)
Contradiction: ATM is not TM-decidable.
This proof used diagonalizationimplicitly…
Re vi ew of Pr oo f (1 )
O M M K L
accept accept M M accept accept accept accept M accept accept M M M M M
4 3 2 1 4321
‘A c c e p ta n c e b e h a v io r’ o f M
io n < M
j>
Re vi ew of Pr oo f (2 )
O M M K L
reject reject accept accept M reject reject reject reject M accept accept accept accept M reject accept reject accept M M M M M
4 3 2 1 4321
‘D e c id in g b e h a v io r’ o f G o n < M
i, < M
j>>
103
M L O M M K L L
accept accept reject reject D reject reject accept accept M reject reject reject reject M accept accept accept accept M reject accept reject accept M D M M M M
4 3 2 1 4321
Re vi ew of Pr oo f (3 )
D is a g re e in g D h a s to o c c u r i n li s t a s w e ll…
104
Re vi ew of Pr oo f (4 )
M L O M M K L L
? accept accept reject reject D reject reject accept accept M reject reject reject reject M accept accept accept accept M reject accept reject accept M D M M M M
4 3 2 1 4321
Contradiction for D on input <D>.
An oth er Vie w of th e P rob lem
T h e “ S e lf -r e fe re n tia l p a ra d o x ” o c c u rs w h e n w fo rc e th e T M D to d is a g re e w ith it s e lf.
O n th e o n e h a n d , D k n o w s w h a t i t i s g o in g to d o o n in p u t < D > , b u t t h e n it d e c id e s to d o s o m e th in g e ls e in s te a d .
“Y o u c a n n o t k n o w fo r s u re w h a t y o u w ill d o in th e fu tu re , b e c a u s e th e n y o u c o u ld d e c id e to c h a n g e y o u r a c tio n s a n d c re a te a p a ra d o x .”
Se lf-R efe ren ce in M ath
T h e d ia g o n a liz a tio n m e th o d im p le m e n ts th e s e re fe re n c e p a ra d o x in a m a th e m a tic a l w a y .
In lo g ic th is a p p ro a c h is o fte n u s e d to p ro v e th a c e rta in th in g s a re im p o s s ib le .
K u rt G ö d e l g a v e a m a th e m a tic a l e q u iv a le n t o f “T h is s e n te n c e is n o t t ru e .”
107
TM -Un rec og niz ab le
ATM is not TM-decidable, but it is TM-recognizable ? Theorem: ATM is recognizable
Proof: It is suffcientto simulate M. Run the M on w. If M accepts, then accept
108
TM -Un rec og niz ab le
ATM is not TM-decidable, but it is TM-recognizable.What about a language that is not recognizable?
Theorem: If a language A is recognizableand its complement Āis recognizable, then Ais Turing machine decidable.
Proof:Run the recognizing TMs for A andĀinparallel on input x. Wait for one of the TMs toaccept. If the TM for A accepted: “accept x”;if the TM for Āaccepted: “reject x”.
Ā
TMis n ot TM -R eco gn iza ble
By the previous results it follows that ĀTM cannotbe TM-recognizable, because this would implythat ATM is TM decidable.
W e c a ll la n g u a g e s li k e Ā
TMc o -T M r e c o g n iz a b le
TM recognizable
co-TM recognizable TM decidable
Th ing s th at TM s C an no t D o:
EQTM = {<G,H>| G and H are TMs with L(G)=L(H) } ETM = {<G>| G is a TM with L(G)=∅} The following languages are also unrecognizable: To be precise:•ETM is co-TM recognizable•EQTM is not even co-Turing recognizable
111
Su m m ing up c o -T
M r e c o g n iz a b le T M -r e c o g n iz a b le
T M d e c id a b le
E
TM= { < M > | M is a T M w ith L (M )= ∅ }
E Q
TM= { < G ,H > | G ,H T M s w ith L (G )= L (H ) } A
TM= { < M ,w > | M is a T M th a t a c c e p ts w } A ll la n g u a g e s
112
Re du cib ility Re du cib ility
Re du cib ility
It required quite some effort to prove that ATM is not TM-decidable.But now we can build on this result as follows:
If “L is TM-decidable”implies “ATM is decidable”,then L is not decidable.
Typical proof outline: Let M be the TM that decides L; with this M as asubroutine, the following TM [….] decides ATM .Conclusion: M is not TM-decidable.
Ha ltin g P rob lem R evi site d
Theorem: The ‘halting problem’languageHALTTM = {<M,w>| the TM M halts on input w }is undecidable(but of course recognizable).
Proof:Let G be a TM that decides HALTTM .The following TM decides ATM :1.On input <M,w>run G to decide halting2.If G rejected<M,w>then “reject”3.If G accepted<M,w>then copy (reject/accept) output of M on w.(Note that this TM always produces an output.)ATM is undecidable, hence such a G cannot exist.
