Argomenti avanzati Introduzione alla calcolabità Ricordiamo alcune nozioni di base Gliargomentitrattati Presentazione

1

Pre se nta zio ne

2

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

5

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 i 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 iti ad elen care so lo i rif erim enti m a c erc hi di rias sum erli e 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 … .)

6

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

9

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)

10

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) ≤c—g(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 ”.

13

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

14

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 ∉ L if a n d o n ly if x ∈ L

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 |)*

17

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 by afinite automaton

A finite (state) automata
a simple machine that reads a singleinput character at every time step
has an internal state that can assumea finite number of different values
internal state are of two different types(accept, reject) that define whetherthe read string is accepted or not 11E132.1 FA(internal state)

18

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 by a 5-tuple 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 deterministic according whether δ(q,a) is a singleton or not for each q,a

19

Fi nit e a uto m ato n

q

1

q

2

q

3

1 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

21

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

}

22

Ex am ple : th e b oo lea n alg eb ra

G=(V,Σ,R,S) with
V = {S,Z}
Σ= {0,1,(,),¬,∨,∧}
R:
S→0
S →¬(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) with
V = {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

25

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 (

C Y X A

PDA(internal state) stack

26

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

n

b

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

S

doe 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

29

Tu rin g Tu rin g m ach ine s m ach ine s

30

Tu rin g M ach ine s

Alan M. Turing (1912–1954)

In1936, Turingintroducedhis abstract model for computation in his article “On Computable Numbers, withan application to the Entscheidungsproblem”.

At the same time, Alonzo Church published similar ideas and results.

TheTuringmodel has becomethestandardmodel intheoretical 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___wwwn21

Initially, 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.

33

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_vvvm21

s ta te q

reject LL_vvvm21

o r

34

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).

37

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 e s 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

i

q

j

b → c ,R

38

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

41

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).

42

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.

45

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.

46

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} k

47

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

1

q

j

a

1

v

1

, u

2

q

j

a

2

v

2

, … , u

k

q

j

a

k

v

k

b y M ’ c o n fig u ra tio n

,

q

j

# u

1

a

1

v

1

# u

2

a

2

v

2

# … # u

k

a

k

v

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 .)

49

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 g : • 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 te • 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 o l, 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 t.

50

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.

53

Bre ad th Fi rst

Let b be the maximum numberof children of a node. C1

C6 C5 C4C3 C2

M “reject”

“accept” t=1t=2t=3 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.

54

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 .

57

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 tworegistersR1e R2

58

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 thatcheckwhetherR2isa factorof R1?

59

µ -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

s

com 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

61

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 ast

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 ed 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?

62

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.

65

(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.

66

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.

69

A

DFA

is 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”

70

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>