{{TIN064 Skripta}} Tato kapitola se věnuje zavedení a základním vlastnostem následujících tříd funkcí: částečně rekurzivní funkce (ČRF), obecně rekurzivní funkce (ORF) a primitivně rekurzivní funkce (PRF). Pokud tyto termíny slyšíte poprvé, doporučuji přečíst si nejprve <TIN064%20Úvod>.

Induktivní výstavba funkcí

Funkce budeme konstruovat induktivně: zavedeme si tři základní funkce (nulová, následník, <#vydělení%20j-té%20složky>) a pak tři operátory (substituce, primitivní rekurze, minimalizace). Operátor je taková "metafunkce" — na vstupu dostane jednu či více funkcí a na výstupu vrátí nějakou novou funkci.

Ke každé funkci, kterou takto zkonstruujeme, pak bude existovat její odvození, což je posloupnost funkcí, z nichž každá je buď základní funkcí nebo vznikla z předchozích funkcí pomocí nějakého operátoru.

Pokud vám to připomíná induktivní výstavbu důkazů v logice, tak si můžete připsat malé nevýznamné plus. Ano, základní funkce jsou paralelou k axiomům, operátory jsou paralelou k odvozovacím pravidlům (modus ponens,...) a odvození funkce je paralelou k odvození důkazu.

Základní funkce

nulová funkce

následník

vydělení j-té složky

Operátory

substituce

primitivní rekurze

minimalizace

Definice ČRF, ORF, PRF

Poznámky

Příklady

sčítání

odčítání

násobení

Ostré inkluze ČRF, ORF, PRF

neostré inkluze

ČRF, která není ORF

ORF, která není PRF

Výpočetní síla TS a ČRF je ekvivalentní

ČRF => TS (každá ČRF je turingovsky vyčíslitelná)

TS => ČRF

Numerace ČRF

Standardní numerace

Gödelova numerace

Každé číslo odpovídá programu?

Kleeneova věta

Znění věty (Kleene, o normální formě, o univerzální funkci)

Náznak důkazu

Co znamená univerzální funkce?

Co znamená predikát T?

Co znamená μy\mu_y?

Co znamená funkce UU?

Co říká s-m-n věta?

Co mám říkat já?

Univerzální PRF a ORF

Neexistuje univerzální PRF pro třídu PRF

Neexistuje univerzální ORF pro třídu ORF