Paweł Pilarczyk - Funkcja Ackermanna.pdf - Logika - junosza1755

FunkcjaAckermanna

Pawe“Pilarczyk

31pa„dziernika2003r.

Streszczenie

Wniniejszejnotatcejestprzedstawionydrobiazgowydow ó dfaktu,»e

funkcjaAckermannaniejestprymitywnierekurencyjna.Jestr ó wnie»

pokazanyzwodniczylemat,napodstawiekt ó regomo»nanatychmiast

uzyska¢powy»szetwierdzenie,leczsamegolematuniedasiƒudowod-

ni¢przezindukcjƒ,cojestr ó wnie»wykazanewniniejszejpracy.

Wstƒp

Niniejszeopracowaniezawieraszczeg ó “owydow ó dnastƒpuj¡cegotwierdzenia:

Twierdzenie1FunkcjaAckermannazadanawzorem

A(0,y)=1,

A(1,0)=2,

A(x,0)=x+2dlax > 2,

niejestprymitywnierekurencyjna.

Dow ó dtenjestuzupe“nieniemdo¢wicze«dowyk“adudrahab.Mar-

kaZaioncapt.Teoriaprogramowania,kt ó reautormia“przyjemno–¢pro-

wadzi¢wInstytucieInformatykiUniwersytetuJagiello«skiegowrokuakad.

2000/2001.

Dlakompletno–ciwywoduponi»ejjestpodanapokr ó tcede nicjaklasy

funkcjiprymitywnierekurencyjnych.

n dlapewnegon2 N wzbi ó rliczbnaturalnych,kt ó ra

zawierafunkcjezerowe:z(x 1 ,...,x n )=0,rzutowania:I n k (x 1 ,...,x n )=x k ,

funkcjƒnastƒpnika:f(x)=x+1orazjestzamkniƒtazewzglƒdunaoperacjƒ

sk“adaniaorazschematrekursjiprostej(zob.te»dow ó dLematu3).

A(x+1,y+1)=A A(x,y+1),y .

De nicja2Klasafunkcjiprymitywnierekurencyjnychtonajmniejszaklasa

funkcjiprowadz¡cychz N

2 Pawe“Pilarczyk

Ewentualnyczytelnikniniejszejnotatkipowinienwiedzie¢,»efunkcjaAc-

keramannajestfunkcj¡rekursywn¡(orazcotoznaczy).Jesttozatemprzy-

k“adfunkcji,kt ó rajestrekursywna,alenieprymitywnierekurencyjna,co

dowodzi,»eklasafunkcjirekursywnychjestistotniewiƒkszani»klasafunkcji

prymitywnierekurencyjnych.

Dow ó dTwierdzenia

Dow ó dTwierdzenia1jestopartynanastƒpuj¡cymlemacie,kt ó rym ó wi,»e

funkcjaAckermannaro–nieszybciejni»dowolnafunkcjaprymitywniereku-

rencyjna:

Lemat3Dladowolnejfunkcjiprymitywnierekurencyjnejfistniej¡takie

sta“en f ,x f 2 N ,»e

8x > x f max{f(x 1 ,...,x n )|x 1 ,...,x n 6 x}<A(x,n f ).

PonadtowdowodzieTwierdzenia1(orazwinnychdowodach)wykorzystuje

siƒnastƒpuj¡c¡prost¡w“asno–¢funkcjiAckermanna:

W“asno–¢4FunkcjaAckermannajestniemalej¡cazewzglƒdunapierwsz¡

izewzglƒdunadrug¡zmienn¡.

Korzystaj¡czLematu3orazzW“asno–ci4,kt ó res¡wykazanedalej,mo»na

ju»udowodni¢,»efunkcjaAckermannaniejestprymitywnierekurencyjna.

Dow ó dTwierdzenia1Niewprost.GdybyfunkcjaAckermannaAby“a

prymitywnierekurencyjna,tonamocyLematu3istnia“ybytakiesta“en A

ix A ,»e

8x > x A max{A(x 1 ,x 2 )|x 1 ,x 2 6 x}<A(x,n A ).

We„myx > max{x A ,n A }.Wtedyzlewejstronyw–r ó dliczbbranychdo

maksimumjestm.in.A(x,x),kt ó remusia“obyby¢mniejszeodA(x,n A ),

atoprzeczy“obymonotoniczno–cifunkcjiAckermannazewzglƒdunadrug¡

zmienn¡(zob.W“asno–¢4).Dow ó dTwierdzenia1jestwiƒczako«czony. 2

Pozosta“edowody

Zanimprzyst¡pimydodalszychdowod ó w,wyka»emy,»ewarto–¢funkcji

Ackermannajestzawszesilniewiƒkszaodjejpierwszegoargumentu.

Obserwacja5Dladowolnychx,y2 N mamyA(x,y) > x+1.

FunkcjaAckermanna 3

( x+1, je»elix=0,1,

x+2 > x+1, je»elix > 2.

Za“ ó »myteraz,»edowodzonanier ó wno–¢jestprawdziwadlapewnegoy2 N .

Wyka»emy,»ejesttakr ó wnie»dlay+1.Wtymceluzauwa»mynajpierw,»e

A(x,y)=

A(x,y+1) > A(0,y+1)+x.

Rzeczywi–cie,dlax=0jesttotrywialne,awprzypadkux>0,korzystaj¡c

zewzorunaAizza“o»eniaindukcyjnego,otrzymujemy

A(x,y+1)=A A(x−1,y+1) ,y > A(x−1,y+1)+1

ipowtarzaj¡ctenproces wyci¡ganiajedynkizxnakoniec takd“ugo,a»x

zostaniewyzerowane(tj.xrazy),uzyskujemy

A(x,y+1) > A(0,y+1)+x=1+x,

coko«czyindukcyjnydow ó dObserwacji5.

Dow ó dW“asno–ci4Korzystaj¡czde nicjifunkcjiAckermannaorazzOb-

serwacji5,otrzymujemydlay>0

A(x+1,y)=A A(x,y) ,y−1 > A(x,y)+1,

cooznaczapouwzglƒdnieniuprzypadkuy=0,kt ó ryjesttrywialny,»efunk-

cjaAjestniemalej¡cazewzglƒdunapierwsz¡zmienn¡.

Przejd„myterazdodowodutego,»efunkcjaAckermannajestniemalej¡ca

zewzglƒdunadrug¡zmienn¡.NamocyObserwacji5mamy

A(x−1,y+1) > x−1+1=x.

Dziƒkiudowodnionejw“a–niemonotoniczno–cizewzglƒdunapierwsz¡zmien-

n¡orazprzypowt ó rnymwykorzystaniuObserwacji5mo»emyst¡duzyska¢

dlax>0

A(x,y+1)=A(A (x− 1, y+1 )

| {z }

> x

,y) > A(x,y),

czyli»¡dan¡monotoniczno–¢zewzglƒdunadrug¡zmienn¡(tutajznowu

przypadekx=0jesttrywialny).

Dow ó dW“asno–ci4zosta“niniejszymzako«czony.

ZanimprzejdziemydodowoduLematu3,udowodnimynastƒpuj¡c¡uwagƒ

techniczn¡daj¡c¡oszacowanienapewneszczeg ó lnezagnie»d»eniefunkcji

Ackermanna:

Dow ó dObserwacji5Indukcyjniezewzglƒdunay.Dlay=0wprost

zde nicjifunkcjiAckermannamamy

4 Pawe“Pilarczyk

Uwaga6Dladowolnegox > 4,m > 0orazy 6 xmamy

A A(...(A(x,m+1) ,m), .. .),m

| {z }

yrazy

6 A(x,m+2).

Dow ó dUwagi6Rozpisuj¡cA(x+y,m+1)zde nicjifunkcjiAckerman-

natakd“ugo,a»wewn¡trzpierwszymargumentembƒdziex=x+y−y

(tj.rozpisuj¡cyrazy),otrzymujemy

(1)A(x+y,m+1)=A A(x+y−1,m+1),m =...

...=A A(...(A(x,m+1),m ,...),m

| {z }

yrazy

Zauwa»myteraz,»e

(2) 2x 6 A(x−1,m+2).

Rzeczywi–cie,korzystaj¡czmonotoniczno–cifunkcjiAckermannazewzglƒdu

naobiezmienne,uzyskujemytoniemalnatychmiast:

A(x−1,m+2)=A A(x−2,m+2

|{z}

> 0

|{z}

> 1

> A A (x − 2,0 )

| {z }

=x,box > 4

,1)=A(x,1)=2x.

Wykorzystuj¡cto,»efunkcjaAckermannajestniemalej¡cazewzglƒduna

pierwsz¡zmienn¡,otrzymujemywpo“¡czeniuznier ó wno–ci¡(2)nastƒpuj¡ce

oszacowanie:

A(x+ y

|{z}

6 2x

,m+1) 6 A(2x,m+1)

namocy(2)

6 A A(x−1,m+2),m+1 =A(x,m+2),

kt ó repouwzglƒdnieniur ó wno–ci(1)ko«czydow ó dUwagi6. 2

Dow ó dLematu3Indukcyjniezewzglƒdunastrukturƒfunkcjif.

a)Dlafunkcjistaler ó wnejzeruwystarczywzi¡¢n f =0,x f =0.

b)DlarzutowaniaI n k dobres¡sta“en f =0,x f =0.

c)Dlanastƒpnika(f(x)=x+1)mo»nawzi¡¢n f =0,x f =2.

d)Je»elifjestz“o»eniemfunkcjih: N

k ! N ifunkcjif 1 ,...,f k : N

n ! N ,

tzn.

f(x 1 ,...,x n )=h f 1 (x 1 ,...,x n ),...,f k (x 1 ,...,x n ) ,

),m+1

FunkcjaAckermanna 5

tomo»nawzi¡¢

x f =max{4,x h ,x f 1 ,...,x f k },

n f =max{n max +1,n h +2},

gdzie

n max =max{n f 1 ,...,n f k }.

Rzeczywi–cie,dlax > x f mamy:

max{h f 1 (x 1 , .. .,x n )

| {z }

<A(x,n f 1 )

,...,f k (x 1 , .. .,x n )

| {z }

<A(x,n f k )

|x 1 ,...,x n 6 x}

bon max > n f i

6 max{h(x 1 ,...,x k )|x 1 ,...,x n 6 A(x,n max )} boA(x,n max ) > x h

<A A(x,n max

|{z}

6 n f − 1

),n h

|{z}

6 n f − 2

6 A A(x,n f −1),n f −2 napodst.Uwagi6

6 A(x,n f ).

e)Je»elifpowstajeprzypomocyschematurekursjiprostejzfunkcjig

ih,tzn.

f(x 1 ,...,x n ,y+1)=h x 1 ,...,x n ,y,f(x 1 ,...,x n ,y) ,

towtedymo»emyobra¢nastƒpuj¡cesta“e:

x f =max{4,x g ,x h },

n f =max{n g +1,n h +2}.

Rozpocznijmydow ó dodwypisaniaodpowiedniegooszacowaniawprzypadku

y=0.Je»elix > x f ,towtedy

max{f(x 1 ,...,x n ,0)|x 1 ,...,x n ,0 6 x}=

=max{g(x 1 ,...,x n )|x 1 ,...,x n 6 x}<A(x,n g )

bon f > n g

6 A(x,n f ).

Przeanalizujmyjeszczeprzypadeky=1.Dlax > x f odpowiednieoszacowa-

niewygl¡danastƒpuj¡co:

max{f(x 1 ,...,x n ,1)|x 1 ,...,x n ,1 6 x}=

=max{h x 1 ,...,x n ,0,f (x 1 ,. .. ,x n ,0 )

| {z }

<A(x,n g )

|x 1 ,...,x n 6 x} 6

6 max{h(x 1 ,...,x n ,y,z)|x 1 ,...,x n ,y,z 6 A(x,n g )},

f(x 1 ,...,x n ,0)=g(x 1 ,...,x n ),

Paweł Pilarczyk - Funkcja Ackermanna.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: