== Kleeneova věta == Toto je jedna z nejdůležitějších vět vyčíslitelnosti, protože většina ostatních je na ní založená. === Znění věty (Kleene, o normální formě, o univerzální funkci) === Pro každé k \ge 1 (libovolný počet proměnných): * Existuje ČRF k+1 proměnných \Psi_k(e, x_1, ..., x_k) taková, že \Psi_k je '''univerzální funkcí''' pro třídu funkcí k proměnných, tedy '''vyčísluje''' e-tou takovou funkci. * ''('''normalizace'''):''
Jde efektivně získat numerace e z odvození ČRF a naopak z e lze získat efektivně odvození ČRF. * ''(Souvislost s Turingovým strojem):''
Existuje PRF jedné proměnné U a PRP k+2 proměnných T_k (Kleeneho T predikát nebo '''Turingův predikát''') takové, že \Psi_k(e, x_1, ..., x_k) \simeq U(\mu_y(T_k(e, x_1, x_2, ..., x_k, y))). (Jak interpretovat U atd. viz níže). * ''('''s-m-n věta'''):''
Existuje PRF m+1 proměnných s_m prostá a rostoucí ve všech proměnných ('''fixace prvních m proměnných''') taková, že \Psi_{m+n}(e, y_1, ..., y_m, x_1, ..., x_n) \simeq \Psi_{n}(s_m(e, y_1, ..., y_m), x_1, ..., x_n) * ''(Univerzální funkce je '''standardní'''):''
T_k(e, x_1, ..., x_k, y)\;\And\; T_k(e, x_1, ..., x_k, z) \Rightarrow y=z === Náznak důkazu === ''Cože zase mám něco dokazovat? A on už někdo dokázal existenci univerzálního Turingova stroje, že? A on už někdo dokázal, že TS má stejnou sílu jako ČRF, že? Tak to by pro ty dva už neměl být takový problém dokázat tohle, ne?'' Jestli čekáte lepší důkaz než tento monolog, tak hledejte, ale o moc exaktnější to asi nebude a rozhodně to nebude elegantnější. Celý důkaz se nedělá ani na přednášce. Důležitější než přesný důkaz je ale pochopit, co znamenají jednotlivé funkce a predikát T. === Co znamená univerzální funkce? === Obecně mějme třídu \mathcal{A} funkcí n proměnných, které mají nějakou vlastnost (např. jsou to PRF, ČRF,...). ''Univerzální funkce'' pro třídu \mathcal{A} je funkce univ, která dostane jako vstup číslo ''e'' a parametry x_1, ..., x_n a vrátí to samé, co by vrátila ''e''-tá funkce z třídy \mathcal{A}.{{Odkaz na poznámku|pozn1}} Důležité je, že takto dostaneme všechny funkce z té třídy, tedy \forall f \in \mathcal{A} \;\;\; \exists e \in \mathbb{N} : f(x_1, ..., x_n) \simeq univ(e,x_1, ..., x_n). To mimochodem znamená, že třída funkcí \mathcal{A} musí být spočetná. Kleenova věta říká důležitou informaci: Existuje '''univerzální funkce pro ČRF ''k''-proměnných''', kterou budeme nazývat \Psi_k. Tato univerzální funkce je navíc sama také ČRF, z čehož plynou zajímavé důsledky. === Co znamená predikát T? === Kleeneho predikát T_1(e, x, y) platí, právě když y= (dvojice zakódovaná jako jedno číslo) a ''e'' je kód funkce jedné proměnné, která se při simulaci na TS nad vstupem x zastaví (přesně) po y_0 krocích s výsledkem y_1. Obecně můžeme zavést predikát T_k(e,x_1,...,x_k,y) pro funkce k proměnných. * Funkce odpovídající predikátu T_k je primitivně rekurzivní. Přesný důkaz je pracný, ale základní myšlenkou je simulace výpočtu TS, přičemž víme, kolik nejvýše kroků je třeba simulovat, takže nám stačí for-cyklus a nepotřebujeme while. * Pro konkrétní TS a zadaný vstup x buďto existuje právě jedna dvojice taková, že po y_0 krocích se stroj zastaví s výsledkem y_1, a nebo neexistuje žádná taková dvojice, pokud se stroj nikdy nezastaví. (Tím jsme dokázali, že je univerzální funkce standardní.) (To ovšem není součástí znění věty, ani to z ní nějak neplyne, pouze to může posloužit jejímu lepšímu pochopení. Jiná možná definice tohoto predikátu je, že y kóduje posloupnost všech konfigurací výpočtu TS nad vstupem x až do jeho zastavení. Pak se odpovídajícím způsobem změní i definice U.) === Co znamená \mu_y? === \mu_y T_1(e, x, y) je funkce dvou proměnných (e a x), která vrátí nejmenší y takové, aby platil predikát T_1(e, x, y). Když už máme sestrojen predikát T (včetně odvození), tak tuto funkci vytvoříme jednoduše pomocí operátoru minimalizace. === Co znamená funkce U?=== U je jednoduchá funkce, která vydělí druhou složku z kódu dvojice. Mimochodem při [[TIN064_Prerekvizity#Kódování n-tic|zavádění kódování dvojic]] jsme si přesně tuto funkci nazvali r (jako right), ale dnes je v módě U. Speciálně funkce U\big(\mu_y T_1(e, x, y)\big) vrátí výsledek ''e''-tého programu (''e''-té ČRFunkce) jedné proměnné spuštěného na vstupu x. Protože to je hodně významná funkce, tzv. ''univerzální pro ČRF 1 proměnné'', zavedeme si pro ni značení \Psi_1(e, x), obdobně \Psi_k(e, x_1,...,x_k) pro ''k'' proměnných. A aby každý věděl, že jak moc hodně významná ta funkce je, tak pro ni zavedeme ještě další značení, \varphi_e, ve kterém se pro stručnost explicitně neuvádí ''k'', ale pozná se to z počtu parametrů , protože \Psi_k(e, x_1,...,x_k) \equiv \varphi_e(x_1,...,x_k). === Co říká s-m-n věta? === Mám číslo ''e'', tedy ''e''-tý program pro m+n proměnných. Rozhodnu se prvních m proměnných zafixovat na hodnotách y_1, ..., y_m a vytvořit tak novou funkci (program) n proměnných; funkcionální podivíni tomu můžou říkat ''curryfikace''. Schematicky zapsáno: nova_funkce(x_1,...,x_n){ return program_s_cislem_e(y_1, ..., y_m, x_1, ..., x_n); } S-m-n věta říká, že můžu snadno zjistit číslo této nové funkce (programu). Existuje totiž sada PRFunkcí s_1, s_2, s_3,... a my použijeme konkrétně s_m(e,y_1, ..., y_m) a získáme tak číslo té nové funkce. === Co mám říkat já? === Nevíte, jak vyslovovat jméno Kleene? Každý to vyslovuje jinak, tak si vymyslete vlastní výslovnost, stejně jako to udělal pan [[wen:Stephen Cole Kleene|Stephen Cole Kleene]]. Zvláště kreativní jedinci si mohou vymyslet hned několik originálních výslovností, aby se nemuseli u zkoušky opakovat. {{Poznámka|pozn1| Pokud f(x_1, ..., x_n)\uparrow, pak i univ(e,x_1, ..., x_n)\uparrow. To, která funkce je vlastně ta e-tá, je definováno právě pomocí univerzální funkce. }}