Barbara Klunder - Podstawy Teorii Obliczalności.pdf - Logika - abi77

Toru«2003

BarbaraKlunder

PodstawyTeoriiObliczalno±ci

Materiałydowykładu

Wwykładzezastanawia¢b¦dziemysi¦naddwomakluczowymipytania-

mi:

Czymjestefektywnaprocedura? Hardwaremczysoftwarem?Urz¡-

dzeniem,którerealizujeokre±loneobliczenia(pierwszekomputery),czyci¡-

gieminstrukcji(programem)wnaszymulubionymj¦zykuprogramowania?

Czymjestproblem rozwi¡zywalnyprzezefektywn¡procedur¦?Czy

istniej¡problemynierozwi¡zywalne?

Intuicyjnieczujemy,»eb¦dziemywykonywa¢ obliczenia .

Zasdaniczoprowadzi¢b¦dziemyobliczeniana(sko«czonychci¡gachliczb)

liczbachnaturalnych.

Przypu±¢my,»echcemyprowadzi¢obliczenianazbiorzewej±¢iwyj±¢X

ró»nymodN.Mo»emytozrobi¢przyporz¡dkowuj¡cka»demuelementowiz

Xliczb¦naturaln¡zwan¡jejkodemtak,abyró»neelementyXmiałyró»ne

kody.

Maj¡cwej±ciazXnale»yzast¡pi¢jeichkodamiiwykona¢obliczenia,które

zwracaj¡numerycznewyj±cie.Je±litowyj±ciejestkodemelementuzX,to

tenelementtraktujemyjakoko«cowywynikoblicze«.

Chcemy,bypierwszyiostatnikroktejprocedurybyłrealizowanywsposób

algorytmiczny.Wtedymówimy,»ekodowaniejestefektywne.

UnasXb¦dzie:zbioremwszystkichsko«czonychci¡gówliczbnaturalnych

lubsłównadustalonym(sko«czonym)alfabetem,zbioreminstrukcjilubpro-

gramówpewnegoj¦zykaitp.

1Kodowaniainumeracje

Przypomnijmydwiedeﬁnicjezbioruprzeliczalnego.

Deﬁnicja1.1 KodowaniemzbioruXnazywamydowoln¡funkcj¦ró»nowar-

to±ciow¡f : X −! N.

Zbiórjestprzeliczalny,je±lijestrównolicznyzpewnympodzbioremN.

Deﬁnicja1.2 Numeracj¡(lubwyliczeniem)zbioruXnazywamydowoln¡

funkcj¦g : N −! X,którajest”na”.

Zbiórjestprzeliczalny,je±lijegoelementymo»naustawi¢wci¡g.

Przykłady

1.Funkcja : N × N −! N okre±lonawzorem ( n.m )=2 n (2 m +1) − 1

jestbijektywnymkodowaniemparliczbnaturalnych.

Funkcjaodwrotnazadanajestprzezfunkcje 1 , 2 : N −! N zdeﬁnio-

wanenast¦puj¡co:

1 ( x )= n wtw,gdy2pojawiasi¦wrozkładziex+1naczynnikipierw-

szezwykładnikiemn;

2 ( x )= 1 2 ( x +1

2.Wtedyfunkcja : N × N × N −! N, ( n,m,p )= ( ( n,m ) ,p )

jestbijektywnymkodowaniemtrójekliczbnaturalnych.Jakwygl¡da

funkcjaodwrotna?

3.Rozwa»myfunkcj¦ : S k> 0 N k −! N tak¡,»e

( a 0 ,a 1 ,...,a k − 1 )=2 a 0 +2 a 0 + a 1 +1 + ... +2 a 0 + a 1 + ...a k − 1 + k − 1 − 1 .

Jesttobijektywnekodowaniewszystkichsko«czonychci¡gówliczbna-

turalnych.

Poka»emypó¹niej,»efunkcje i s¡(RAM-)obliczalne,anumeracja − 1

jestefektywna.B¦d¡tokluczowerezultatytechniczne.

2MaszynyRAM

2.1Maszynyznieograniczon¡pami¦ci¡RAM(She-

perdson&Sturgis)

Budowamaszynyrealizuj¡cejprogramywj¦zykuzbli»onymdopopularnych

imperatywnychj¦zykówprogramowania,któryb¦dziemyrozwa»a¢,przypo-

minabudow¦rzeczywistychkomputerów:maszynaskładasi¦zlicznikaroz-

kazóworazpami¦ci,którajesttablic¡rozmiaru @ 0 .Komórkipami¦cis¡nu-

merowanekolejnymiliczbaminaturalnymiimog¡zawiera¢,takjaklicznik

rozkazów,dowoln¡liczb¦naturaln¡.Wczasieoblicze«prawiewszystkieko-

mórkipami¦cizawieraj¡liczb¦0.

Oznaczenie z[x]oznaczazawarto±¢komórkionumerzex.

ListainstrukcjiRAM

2 1 ( x ) − 1)

Kod

adresów Oznaczenie Semantyka Uwagi

0 n Z(n) z[n]:=0 Licznikrozkazów

zwi¦kszo1

1 n S(n) z[n]:=z[n]+1 Licznikrozkazów

zwi¦kszo1

2 ( m,n ) T(m,n) z[n]:=z[m] Licznikrozkazów

zwi¦kszo1

3 ( m,n,q ) I(m,n,q)

ifz[m]=z[n]

thengotoq

Licznikrozkazów

zwi¦kszo1,

gdyz[m] 6 =z[n],

wprzeciwnymprzypadku

umie±¢wnimq

Instrukcjetypu0,1,2nazywamyarytmetycznymi,atypu3warunkowy-

mi.

Deﬁnicja2.1Programem (naRAM)nazywamydowolnyniepustyci¡g

RAM-instrukcji.

Semantykainstrukcjitypu3wymuszanumerowanieinstrukcjiwprogramie.

Kulturamatematycznawymagaodnassformalizowaniapoj¦¢

stanu,instrukcji,semantykiprogramuitp.Wrócimydotegowroz-

dziale4.Naraziewykorzystamynasz¡intuicj¦.

Przykładowyprogram

0I(1,2,5)

1S(2)

2S(3)

3I(1,2,5)

4I(1,1,1)

5T(3,0)

Coliczytenprogram?

Oczywi±cieinteresuj¡naskomórkipami¦ci,któres¡aktywnewczasieobli-

cze«.Programzatrzymujesi¦,gdyz[1]=z[2].Je±liwi¦cnapocz¡tkuz[2] ¬ z[1],

towykonujesi¦zwi¦kszaniez[2],a»równo±¢staniesi¦prawdziwa.Zwi¦ksza

si¦z[3]oilo±¢dodawa«,czyliz[1]-z[2].Je±liwi¦cz[i]oznaczapocz¡tkow¡

zawarto±¢komórki,topozako«czeniuoblicze«wkomórceonumerze0znaj-

dujesi¦liczbaz[3]+z[1]-z[2].Zauwa»my,»eprogramniezatrzymasi¦,gdyna

pocz¡tkuz[2] > z[1]!

ZcharakteruRAMwynika,»eb¦dziemyzajmowa¢si¦programami,które

nawej±ciubior¡ci¡gi(ustalonejdługo±ci)liczbnaturalnychizwracaj¡jedn¡

Kod

instrukcji

liczb¦naturaln¡.

Umowa:Programzwracazawarto±¢komórkionumerze0.

Oczywi±cieniezawszeprogrammusisi¦zatrzyma¢naka»dychdanych.

Naturalnejestwi¦cpytaniejakiefunkcjes¡obliczaneprzezRAM-programy.

B¦dzietopierwszyproblem,którymsi¦zajmiemy.Oka»esi¦,»efunkcjearyt-

metycznes¡RAM-obliczalne.

Deﬁnicja2.2 Niechk > 0 .ProgramPobliczafunkcj¦cz¦±ciow¡f : N k −!

N,je±lipoumieszczeniuci¡gudanychxwkomórkachz[1],...,z[k],wyze-

rowaniupozostałychiuruchomieniuP,Pzatrzymasi¦zwracaj¡cwarto±¢f

nadanychx,dokadniegdyx 2 Dom f.

P .

Symbolem C k oznaczymyzbiórwszystkichfunkcjiRAM-obliczalnychik-

argumentowych.

Przyklad1 NagruncieaksjomatykiPeanoliczbnaturalnychdodawanie

deﬁniujesi¦rekurencyjnie:

x+0=x

x+(y+1)=(x+y)+1

Nieformalnie:nale»ydoxdoda¢1y-razy.OtoprogramRAMobliczaj¡cy

z[1]+z[2],przyzało»eniu,»ez[3]=0.

0I(2,3,5)

1S(1)

2S(3)

4I(1,1,0)

5T(1,0)

(

x − 1gdy x 1

0 gdy x =0 .Funkcjatajestobli-

Przykład2 Niech x ÷ 1=

czanaprzeznast¦puj¡cyprogram.

0I(1,4,9)

1S(3)

2I(1,3,6)

3S(2)

4S(3)

5I(1,1,2)

6T(2,0)

Ka»dyprogramPobliczapewn¡funkcj¦k-argumentow¡,dla k > 0,któr¡

oznaczymysymbolem ( k )

Barbara Klunder - Podstawy Teorii Obliczalności.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: