REKURZIVNÍ  FUNKCE

 

 

1897  1. mezinárodní matematický kongres Curych

 

6. 8. – 12. 8. 1900  2. kongres Paříž (226 účastníků – 90 Francie, 25 Německo, 17 USA, 15 Itálie atd.)

 

Předseda H. Poincaré (1854 – 1912), čestný předseda Ch. Hermite (1822 – 1901).

 

6 sekcí:

1.   Aritmetika a algebra (předseda D. Hilbert (1862 – 1943), tajemník É. Cartan (1869 – 1951))

2.   Analýza (Paul Painlévé (1863 – 1933), J. Hadamard (1865 – 1963))

3.   Geometrie (J. Darboux (1842 – 1917))

4.   Mechanika a matematická fyzika

5.   Historie matematiky

6.   Výuka a metodologie matematiky

 

 

 

8. 8. 1900 Hilbertova přednáška Matematické problémy

 

        „…Síla badatele se uplatňuje při řešení problémů: nachází nové metody, nová hlediska, objevuje širší a svobodnější horizonty.

… Zmiňme se ještě krátce o tom, které jsou všeobecné požadavky, které je právem třeba klást na řešení jakéhokoliv matematického problému. Především mám na mysli požadavek, abychom se mohli přesvědčit o správnosti odpovědi konečným počtem logických závěrů, a to na základě konečného počtu předpokladů, které vyplývají z podstaty úlohy a musí být v každém případě přesně formulovány. … požadavek přesnosti, který se v matematice stal už příslovečným, odpovídá obecné filozofické potřebě našeho rozumu.

… Tato podivuhodná skutečnost (spolu s jinými filozofickými důvody) nás vede k přesvědčení, které určitě sdílí každý matematik – které však nicméně až dosud nikdo nepotvrdil důkazem – k přesvědčení o tom, že každý matematický problém je možno tak či onak rozhodnout; buďto v tom smyslu, že bude ukázána nemožnost rozřešení problému a spolu s tím dokázána nutnost nezdaru všech pokusů o jeho řešení.

… Toto přesvědčení o rozhodnutelnosti každého matematického problému je pro nás silnou pobídkou v průběhu naší práce; slyšíme v sobě neustálé volání: Zde je problém, hledej řešení. Můžeš ho najít pomocí čistého myšlení, protože v matematice neexistuje (nepoznatelné) Ignorabimus.

 

 

 

Diofantická rovnice

 

P(x1, x2, …, xn) = 0,

 

kde  P  je polynom s celočíselnými koeficienty. Řešením této rovnice je každá n-tice celých čísel, která tento polynom anuluje.

 

Již EUKLEIDES (3. stol. př. Kr.) například našel všechna řešení rovnice

x2 + y2 = z2 .

 

 

DIOFANTOS (3. stol.) řešil rovnice 2. stupně ve 2 proměn-ných.

 

Velká Fermatova věta.

 

1768 LAGRANGE (1736 – 1813): vyřešil obecně problém rovnic 2. stupně ve dvou proměnných.

 

HILBERT: Buď dána diofantická rovnice s libovolnými neznámými a s celočíselnými koeficienty. Je třeba najít metodu, která by umožnila po konečném počtu operací rozhodnout, má-li tato rovnice řešení v celých číslech.

 

1900 Alex THUE (1863 – 1922) Buď  f(x)  polynom s celočíselnými koeficienty, jehož všechny sčítance jsou stupně alespoň třetího a který není součinem dvou nebo více polynomů stupně alespoň prvního. Pak rovnice

f(x,y) = c , c celé

nemůže mít nekonečně mnoho celočíselných řešení.

 

Z jeho řešení však nebylo možno najít interval, v němž řešení leží, ani z něho neplynul algoritmus pro nalezení těchto řešení. Tento algoritmus nalezl v r. 1966 Alan BAKER (*1939).

 

1938 nalezl řešení jistého speciálního typu Thoralf Albert SKOLEM (1887 – 1963).

 

Až do vybudování teorie algoritmů byly hledány metody řešení alespoň jistých typů diofantických rovnic. Nepodařilo se však vyřešit ani nejjednodušší typ – rovnice ve dvou proměnných. (Rovnice s jednou proměnnou lze řešit snadno – plyne to z tzv. BEZOUTOVY věty – Etienne BEZOUT (1730 – 1783) .)

 

Polovina třicátých let – teorie algoritmů  Alan Mattison TURING (1912 – 1954), Alonzo CHURCH (1903 -- 1995).

 

Podezření, že problém nemá řešení.

Poznámka: Můžeme se omezit na řešení v přirozených číslech – plyne z Lagrangeovy věty.

 

Hierarchie: funkce – vyčíslitelná funkce – efektivně vyčíslitelná funkce.

 

Formalizací vznikl pojem rekurzivní funkce.

 

Chceme popsat jistou třídu funkcí zobrazujících  (N0)k  do N0 .

Jisté „jednoduché“ funkce zvolíme za základní. Budou to všechny konstantní funkce (později uvidíme, že stačí vzít jen funkci nulovou).

Dále sem zařadíme funkci následovníka – tj. funkci 

 

S(x) = x+1

 

a spočetnou množinu „projektivních“ funkcí

 

Im,n(x1, x2, … , xn) = xm .

 

Rekurzivní funkce je nyní každá funkce, kterou z těchto základních funkcí obdržíme tím, že na ně konečně mnohokrát aplikujeme operátory substituce, primitivní rekurze nebo minimalizace.

 

Operátor substituce  Sm,n  je definován takto:

 

jsou-li dány funkce

h(x1, … , xm), g1(x1, … , xn), … , gm(x1, … , xn),

pak

 

Sm,n(h,g1, …, gm) = h[g1(x1, … , xn), … , gm(x1, … , xn)] =

                                = f(x1, … , xn) .

 

Těchto operátorů je zřejmě spočetně mnoho.

 

Spočetně mnoho je i operátorů primitivní rekurze  Rn .

 

Mějme funkce

g (x1, … , xn) a  h(x1, … , xn, xn+1,xn+2) .

Pak

Rn(g,h) = f(x1, … , xn+1),

kde

                f(x1, … , xn, 0) = g(x1, … , xn)

                f(x1, … , xn, y+1) = h[x1, … , xn, y, f(x1, … , xn, y)] .

 

Operátor minimalizace umožňuje přecházet od již sestrojené funkce  f(x1, … , xn+1)  k funkci  g(x1, … , xn)  takto:

 

Předpokládejme, že pro každou n-tici   [x1, … , xn]  existuje alespoň jedno xn+1  takové, že f(x1, … , xn, xn+1) = 0 . Pak

g(x1, … , xn)  je nejmenší  xn+1  takové, že

f(x1, … , xn, xn+1) = 0 .

 

Každá rekurzívní funkce je efektivně vyčíslitelná.

 

Předpoklad:

 

Churchova téze: Efektivně vyčíslitelné funkce jsou právě všechny rekurzivní funkce.

 

Množina  A  nezáporných celých čísel se nazývá rekurzivní, jestliže její charakteristická funkce je rekurzivní. Množina se nazývá rekurzivně spočetná, je-li oborem hodnot nějaké rekurzivní funkce.

 

Věta: rekurzivní Þ rekurzivně spočetná

 

Věta: Hromadný rozhodovací problém  pro množinu  A  nezáporných celých čísel je algoritmicky řešitelný právě tehdy, když je  A  rekurzivní.

 

Příklady:

·       je-li  A  množina všech prvočísel, je problém algoritmicky řešitelný

·       rozhodnout, zda je formule výrokového kalkulu dokazatelná je algoritmicky řešitelné

·       totéž pro formule predikátového kalkulu není algoritmicky řešitelné

 

Formulace Hilbertova problému: Existuje algoritmus, který by pro každou diofantickou rovnici rozhodl, zda má řešení?

 

Množina  přirozených čísel se nazývá diofantická, jestliže  její prvky jsou právě všechna řešení nějaké diofantické rovnice  P(y, u1, … ,um) = 0 .

Například množina  {0, 1, 4, 9, 16, …}  je diofantická; příslušný polynom je  P(y, u) = y – u2 .

 

Věta: Aby byl 10. problém algoritmicky řešitelný, musí být každá diofantická množina rekurzivní.

 

Je tedy nutno dokázat toto tvrzení nebo najít alespoň jednu diofantickou množinu, která není rekurzivní.

 

Zobecnění diofantické množiny:

Množina  A Í Nn  je diofantická, jestliže existuje nějaká diofantická rovnice taková, že

 


 


Příklady diofantických množin:

 

{[x, y, z]; z = x + y},   {[x, y, z]; z = xy} .

 

V další historii sehrála důležitou roli otázka:

 

Je množina  E = {[x, y, z]; z = xy} diofantická?

 

 

 

Terminologie: například ternární predikát z = x + y  je pravdivý například pro trojice  [3, 2, 5] a [8, 6, 14] a nepravdivý například pro trojici  [1,1,1].

 

n-ární predikát  t(y1, … , yn ) se nazývá diofantický, je-li množina

{[y1, … , yn]; t(y1, … , yn ) je pravdivý}

 

diofantická.

 

Příklady diofantických predikátů:

m1(x, y, z): z = x2 + y2 , m2(x, y): x < y , m3(x, y): x ≤ y .

 

 

Binární predikát m(x, y) se nazývá predikát exponenciálního růstu, jestliže z pravdivosti  m(x, y)  vyplývá  y ≤ xx  a přitom pro každé přirozené  k existují čísla  x,y  taková, že  1 ≤ x , m(x, y)  je pravdivý  a  xk < y .

 

Problém: existuje takový predikát?

 

1952 Julia Robinsonová: Pokud existuje alespoň jeden diofantický predikát exponenciálního růstu, je výše uvedená množina  E  diofantická.

 

1961   Robinsonová, M. Davis, H. Putnam: Pokud je  E  diofantická, je každá rekurzivně spočetná množina diofantická.

 

Víme však, že existují rekurzivně spočetné množiny, které nejsou rekurzivní. Dokáže-li se tedy, že  E  je diofantická, existují diofantické množiny, které nejsou rekurzivní, takže 10. Hilbertův problém není řešitelný.

 

Podle Robinsonové však k tomu stačí najít alespoň jeden diofantický predikát exponenciálního růstu.

 

1970 J. V. MATIJASEVIČ: takový predikát existuje!

 

 

Označme  Fn  n-té Fibonacciho číslo.

Φ(u,v): v = F2u .

 

Φ(u,v)  je pravdivý pro dvojice  (0, 0), (1, 1), (2, 3), (3, 8), (4,21), (5, 55), … .

 

Z vlastností Fibonacciho čísel poměrně snadno plyne, že Φ(u,v) je predikát exponenciálního růstu. Je však třeba ještě dokázat, že je diofantický.

 

Věta:  v = F2u  právě tehdy, když existují přirozená čísla 
            g, h, k, m, n, x, y, z taková, že platí následující vzta
            hy:

1.   u ≤ v < m

2.   m2 – mz – z2  = 1

3.   g2 – gh – h2 = 1

4.   m2 │g

5.   m │(n -2)

6.   (2h + g) │(n - 3)

7.   x2 – nxy +y2 = 1

8.   m │(x - u)

9.   (2h + g) │(x - y)

 

Důsledek: Φ(u,v) je diofantický.

 

 

 

 

DODATEK

 

1960 H. PUTNAM: Existuje takový polynom 

Q(y1, … ,yk,z) pátého stupně s celočíselnými koeficienty, že každou rekurzivně spočetnou množinu  M  přirozených čísel lze získat jako množinu nezáporných hodnot polynomu Q(y1, … ,yk, aM) , kde  aM  je konstanta, kterou lze efektivně vypočítat na základě znalosti rekurzivní funkce  f  takové, že  M = {f(x); x Î N0} .

 

Důsledek: existuje polynom 5. stupně takový, že například všechna prvočísla jsou jeho nezápornými hodnotami.

 

 

Velká Fermatova věta.