7.4. A programkonstrukciók és a kiszámíthatóság

68

7. PROGRAMKONSTRUKCIÓK

7.4. A programkonstrukciók és a kiszámíthatóság Ebben az alfejezetben kis kitér˝ot teszünk a kiszámíthatóság-elmélet felé, és megmutatjuk, hogy az imént bevezetett három programkonstrukció segítségével minden – elméletileg megoldható – feladatot meg tudunk oldani. Ehhez kapcsolatot létesítünk a kiszámítható függvények és a “jól konstruált” programok között.

7.4.1. Parciális rekurzív függvények

A Church tézis szerint a kiszámítható függvények halmaza megegyezik a parciális rekurzív függvények halmazával. A kiszámíthatóság ezen modelljében csak típusú függvények szerepelnek. Elo˝ ször az alapfüggvényeket definiáljuk:

"!$#%&

'(*) +-/, . / 0001 2 : -/, 3. / 0001 !4%3

'( 56879%30:0 '; <>=?@ , . / 000A1
:

A továbbiakban definiálunk néhány elemi függvény-operátort:

6J . Az és H kompozíciója az H I G HLK M2 NO J , PLQARTS !4U PVSXW Y PZQ&[ és ZP Q\RTS : HLK ] ! H 1A0 DE FG

Kompozíció Legyen alábbi függvény:

és

Vegyük észre, hogy ez az operátor megegyezik az alapfogalmaknál bevezetett relációk közötti kompozícióval (tulajdonképpen a szigorú kompozícióval, de függvények esetén ez a kett˝o azonos).

rögzített, és 5`79%30:0 ^ ; @ N ab c . E függvények ^ _ def000T J ghij &k2lDmmmnl 3o P S kTp S1q psrsrsr p S o. ! t J PVS c és uniója / , @:u / P S k p S q psrsrsr p S o . : , / Tfe000Ad J "! / A000T J 1A0 ' v6hw és H x e w . Az függvény H Rekurzió Legyen rögzített, 2 x / O , és szerinti rekurziója y H / 0001 A y H 0 0/ 0A1 000 1 #|%z%z{! ^ {! H / 000} ^ y H / 000A} ^ 1A0 y H /

Unió Legyen

A függvényhez hasonlóan rekurzívan definiálhatnánk ennek a függvénynek az értelmezési tartományát, de ez kívül esik a jelenlegi vizsgálódásunk körén. Ezért csak azt mondjuk, hogy az értelmezési tartomány azon pontok halmaza, ahonnét kiindulva a fenti rekurzió elvégezheto˝ .

69

7.4. A PROGRAMKONSTRUKCIÓK ÉS A KISZÁMÍTHATÓSÁG

_4 3x / . A -operátort erre a függvényre alkalmazva ] h ! U 0001 W / 000Afüggvényt 1 !4%kapjuk, 5 amelyre 79%30:0 %AP; $, S . / 0001 / 15 PV S [ , 000} P S . : és / , 2 ] / 000A1 ! 5 ' U W / 000A} !4% [ 0

-operátor Legyen azt a

A fenti alapfüggvények és a bevezetett operátorok segítségvel már definiálható a parciális rekurzív függvények halmaza.

'6 6

28. DEFINÍCIÓ : PARCIÁLIS REKURZÍV FÜGGVÉNY Az függvény akkor és csak akkor parciális rekurzív, ha az alábbiak egyike teljesül:

az alapfüggvények valamelyike kifejezhet˝o a fenti operátorok parciális rekurzív függvényekre történo˝ alkalmazásával.

7.4.2. A parciális rekurzív függvények kiszámítása

"

Ahhoz, hogy a fenti függvényeket kiszámító programokat tudjunk adni, definiálnunk kell az ilyen függvények által meghatározott feladatot. Legyen egy tetsz˝oleges függvény ( rögzített). Az által meghatározott feladat specifikációja:

1'

! l 000 l l l 000 l / /

! l 000 l / > / ! / mmm g ! / 0001 Y VP S > / 000 !h / 0001 }

Most megmutatjuk, hogy minden parciális rekurzív függvény által meghatározott feladat megoldható “jól konstruált” programmal (jól konstruáltnak tekintünk egy programot, ha elemi programokból a fenti három konstrukcióval megkapható). A bizonyításhoz csak annyit kell feltételeznünk, hogy az alapfüggvények kiszámíthatók (megengedett) elemi programokkal. A fenti feltételezést felhasználva elegendo˝ azt megmutatni, hogy az elemi függvény-operátorok (kompozíció, unió, rekurzió, -operátor) kiszámíthatók jól konstruált programokkal. Kompozíció

E( i

H 6J . Ekkor az HZK ! l 000 l l l 000 l / / J

! l 000 l /

Legyen specifikációja:

és

által meghatározott feladat

70


> / | ! / mmm g ! > / 000 ! ZH K ]

/ 0001 PZQ\RTS / 000A1 } 000 ! 0001 Jelöljük / 000A ! / 000 -mel azt a programot, amely kiszámítja -et, -nel azt, amelyik kiszámítja H -t. Tegyük fel, J H / és hasonlóan / hogy ez a két program vagy elemi értékadás, vagy jól konstruált program. Ebben az esetben a két program szekvenciája kiszámítja H K -et, azaz megoldja a fent speci

fikált feladatot. Legyen el˝ofeltétele:

a második program

utófeltételhez tartozó leggyengébb

> H / 000 "! ZH K ] / 000} / 000 Y P Q utófeltételhez tartozó leggyengébb elo˝ Most vizsgáljuk meg az els˝o program ezen

feltételét:

/ 000A HLK ]

0 !v00A} / 2 0001 /

A00 0A} ! H / 0000001} 1"! / P Q / P S

Könnyen látható, hogy ez a leggyengébb elo˝ feltétel következik -ból, és így a szekvencia levezetési szabálya és a specifikáció tételének alkalmazásával beláttuk, hogy a

/ 000A !h / 000 J ! H

/ 0001 / 000A

program megoldja a fent specifikált feladatot, azaz kiszámítja Unió

^ ! l 000 l l / l 000 l // /k . l .. l 000 l ! J / l 000 l J 3o / > / !| / mmm g > / / 000A / k

és

H

kompozícióját.

5V 97 %30:0 ^ ; @ O c . Ekkor az e függvények l

Legyen rögzített, és uniója által meghatározott feladat specifikációja:

! / 0001 P S k psrsrsr p S o . 000 J / 000A J o "! / 00, A0 d J / 000A1 1 Tegyük fel, hogy a komponens függvények 000kiszámíthatók @ c ! @ / jól00konstruált 0} az 5 prog@ / rammal, vagy elemi értékadással. Jelölje -edik % |5 ^ kiszámító programot. Ekkor ezeknek a programoknak a szekfüggvényt utófeltételhez venciája megoldja a fenti feladatot. Legyen J a ^ -adik program tartozó leggyengébb el˝ofeltételét: J > / / 000 / ?k 000 J / / 000A J / o k d J / 000A} 1 ! / 000T J / 000} / 0001 PVS o

71


5v7 %&090 ^ %;

@

5

@x /

Továbbá minden esetén jelölje az -edik program -hez tartozó leggyengébb el˝ofeltételét. Könnyen látható, hogy az értékadás leggyengébb el o˝ feltételére vonatkozó szabályt alkalmazva:

/ > / / 0001 A000T J / 000A1 } ! / 000d J / 0001 / 000} Y PVS k mmm / 000} Y PVS o Ha most -t és / -et összehasonlítjuk, észrevehetjük, hogy megegyeznek. A szekvencia levezetési szabálya és a specifikáció tétele alapján a

/ / 000 / ?k !v / / 000A1 .. .

! J / 0001 J / 000 J o h program megoldása a fent specifikált feladatnak, azaz kiszámítja

Rekurzió

'

/ 000d J

-t.

e H x

4 j

Legyen rögzített, és . Tegyük fel, hogy mindketten kiszámíthatók jól konstruált programokkal vagy egyszer˝u értékadásokkal. Az függvény szerinti rekurziója által meghatározott feladat specifikációja:

H

! l 000 l

l / 3x /

! l 000 l / 3x / > / ! / mmm g x / !| x / / 000A} x / P S p Q . , > ! y H / 0001 3x / } ! / 0001 illetve ! Jelölje az ez -et és a H -t kiszámító programot 0 0 0 1 x . Oldjuk meg a feladatot egy olyan ciklussal, amelynek invariáns tuH / lajdonsága: > ^ 87 %&090 x / ; ! y H / 000} ^ 1

A ciklus levezetési szabályát vizsgálva azt találjuk, hogy -ból nem következik . Ezért adunk egy olyan feltételt, amelyb˝ol már következik , és adunk egy programot, amely -ból -be jut (így a megoldóprogram egy szekvencia lesz, amelynek második része egy ciklus). Legyen az alábbi:

> ^ ! % !h / 0001 1 !F%3d / 000} szimultán értékadással elérhet˝o. Az értékadás legEz a ^ gyengébb el˝ ofeltételére vonatkozó szabály felhasználásával könnyen látható, hogy az következik -ból. ! 3x / A ciklus levezetési szabályának második pontja alapján a ciklusfeltétel ^ !N x / D^

lesz. A harmadik pontnak megfelel˝oen válasszuk a kifejezést termináló függvénynek. Az ötödik pont azt írja le, hogy az imént definiált termináló fügvény értékének a ciklusmagban csökkennie kell. Ez elérheto˝ a eggyel való növelésével.

^

72


A négyes pont kielégítéséhez vizsgáljuk meg, hogy mi lesz a leggyengébb el o˝ feltétele a -t növel˝o értékadásnak a -re vonatkozóan.

^

!

! ^ #|%Z 79%30:0 x / ; ! y H / 0001 ^ #|%z1A0 Most már – a szekvencia szabálya alapján – csak egy olyan programot kell !h ^ levezetési találnunk, amelyre ! x / 000A} . Ez a program a rekurzió definíció ^ lesz. jához illeszked˝oen épp H /

^ ! ^ #|%3

Így a szekvencia és a ciklus levezetés szabálya valamint a specifikáció tétele garantálja, hogy a

^ ! !

y H

program megoldja a rekurzióját.

%&d / 000A1 ^ !| x / H / ! 000#|} % ^ ^ ^

által meghatározott feladatot, azaz kiszámítja

H

szerinti

-operátor

_ x /

]

Legyen , és tegyük fel, hogy vagy jól konstruált programmal. Tekintsük a

! l 000 l l

kiszámítható egyszer˝u értékadással által meghatározott feladatot:

/

l mmm g !| / 000A} x / P S . , ] / 000A1 1 !v / 0001 1 x / az -et kiszámító programot. Oldjuk meg a felaJelölje datot egy olyan ciklussal, melynek invariánsa: > !h / 000A} 5 87 %&090 %A; / 000} }5 ! %z !b / 000} %-\% szimultán értékadással teljesíthet˝o. Az invariáns a

! l 000 / > / !| / > !

Könnyen látható, hogy ennek a programnak a tele

!| / 000A1 %-\%

! % 4 / 000} M!a% !

!

-re vonatkozó leggyengébb el o˝ felté-

/ 000} %z6!v / 000A} 5 87 %&090:% %; / 0001 15

%z ! %z

következik -ból. A ciklus levezetési szabályának második pontja alapján a ciklusfeltétel lesz. A feladat el˝ofeltétele garantálja, hogy van olyan szám, amelyre fennáll. Legyen egy ilyen tulajdonságú, rögzített természetes szám. Ennek az értéknek a segítségével definiálhatjuk a termináló függvényt: . Ez kielégíti a levezetés szabály harmadik pontját. Az ötödik pont megkívánja, hogy a termináló függvény a ciklusmag lefutása során csökkenjen. Ezt elérhetjük eggyel való növelésével.

73


A negyedik pont teljesítéséhez legyen leggyengébb el˝ofeltétele:

ennek a növelésnek a

!h / 000A} #|%z 5" 79%30:0 Most egy programot a ! h már / csak 0001találnunk #|%z kell értékadásra teljesül, hogy ! % $ !v / 0001 >

-re vonatkozó

%; / 0001 15 ! %z ! %- és állítások közé. A #|%zA \0

A specifikáció tétele, valamint a ciklus és a szekvencia levezetési szabálya garantálja, hogy a

!| / 000} %-\% !4 % !v / 000A1 #% ! #%

program megoldja a

]

által meghatározott feladatot, azaz kiszámítja

] -et.

7.4.3. Következmény Az el˝oz˝oekben megmutattuk, hogy ha az alapfüggvények kiszámíthatók egyszer˝u értékadással, akkor a bel˝olük – a parciális rekurzív függvényeknél megengedett – operátorokkal felépített függvények kiszámíthatók jól konstruált programokkal. A Church tézis szerint a kiszámítható függvények halmaza megegyezik a parciális rekurzív függvények halmazával. Ezek alapján kimondhatjuk az alábbi tételt: 17. TÉTEL : S TRUKTURÁLT PROGRAMOZÁS ÉS KISZÁMÍTHATÓSÁG Minden kiszámítható függvény kiszámítható egy jól konstruált programmal.

7.4.4. Relációk Eljutván az el˝oz˝o tételhez, fordítsuk most figyelmünket a relációk felé. Ahhoz, hogy a relációk kiszámíthatóságát megvizsgálhassuk, definiálnunk kell a kiszámítható reláció fogalmát.

6J l 6J

29. DEFINÍCIÓ : R EKURZÍVAN FELSOROLHATÓ RELÁCIÓ Legyen tetsz˝oleges reláció. akkor és csak akkor rekurzívan felsorolható, ha van olyan parciális rekurzív függvény, amelynek értelmezési tartományára: .

( e J P S !

A kiszámíthatóság-elmélethez igazodva, a továbbiakban csak rekurzívan felsorolható relációkkal fogunk foglalkozni. Ahhoz, hogy megmutassuk, hogy minden kiszámítható (rekurzívan felsorolható) feladat – emlékezzünk, hogy minden feladat egy reláció – megoldható strukturált programmal, elo˝ ször megadjuk a rekurzívan felsorolható relációk egy másik jellemzését.

18. TÉTEL : K LEENE [1936] Ha egy tetsz˝oleges reláció, akkor az alábbi három állítás ekvivalens: (1)

rekurzívan felsorolható

74


(2) (3)

!

egy

parciális rekurzív függvény értékkészlete vagy

egy

rekurzív függvény értékkészlete.

Ennek a tételnek a bizonyítása lásd Ref??? konstruktív, azaz megadja mind , mind pedig felépítését. Mi ezt a függvényt fogjuk használni a kiszámítható feladatunk megoldóprogramjában. Legyen egy rekurzívan felsorolható reláció, és jelölje az elo˝ z˝o tétel konstrukciójával kapott (totális) rekurzív függvényt. Specifikáljuk a feladatot az alábbi módon:

6J l 6J

! 6J l 6J

!`6J > 2!C > n Y P Ez a feladat megoldható egy olyan ciklussal, amelynek invariáns tulajdonsága: 5" 6! 5 } > g

A ciklus levezetési szabályának felhasználásával könnyen belátható, hogy az alábbi program megoldása a fenti feladatnak:

5T ! %3 %z ! C ! 5 #|%z 5 !C5]#%

A bizonyításban a termináló függvény megadásánál ugyanazt a technikát alkalmazzuk, mint a -operátornál. Ezzel az el˝oz˝oleg függvényekre kimondott tételünket általánosíthatjuk relációkra: 19. TÉTEL : S TRUKTURÁLT PROGRAMOZÁS ÉS KISZÁMÍTHATÓ RELÁCIÓK Minden kiszámítható reláció kiszámítható egy jól konstruált programmal. Megjegyzés Az egyetlen feltevés, amit a fenti meggondolásokban használtunk az volt, hogy az alapfüggvények kiszámíthatóak. Így aztán ezek az eredmények kiterjeszthet o˝ k a relatíve kiszámítható függvények (ugyanezen operátorokkal egy tetsz o˝ leges alaphalmazból képzett függvények), vagy a parciális rekurzív funkcionálok halmazára is (Ref[1, page 174]).

7.4. A programkonstrukciók és a kiszámíthatóság

Recommend Documents