﻿\section{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á.

\subsection{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 '\mathit{univerzální funkcí}' pro třídu funkcí $k$ proměnných, tedy '\mathit{vyčísluje}' $e$-tou takovou funkci.

* \mathit{(}'normalizace'\mathit{):}<br/> Jde efektivně získat numerace $e$ z odvození ČRF a naopak z $e$ lze získat efektivně odvození ČRF.

* \mathit{(Souvislost s Turingovým strojem):}<br/> Existuje PRF jedné proměnné $U$ a PRP k+2 proměnných $T_k$ (Kleeneho T predikát nebo '\mathit{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).

* \mathit{(}'s-m-n věta'\mathit{):}<br/> Existuje PRF m+1 proměnných $s_m$ prostá a rostoucí ve všech proměnných ('\mathit{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)$

* \mathit{(Univerzální funkce je }'standardní'\mathit{):}<br/> $T_k(e, x_1, ..., x_k, y)\;\And\; T_k(e, x_1, ..., x_k, z) \Rightarrow y=z$

\subsection{Náznak důkazu}

\mathit{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$.

\subsection{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,...). 
\mathit{Univerzální funkce} pro třídu $\mathcal{A}$ je funkce $univ$, která dostane jako vstup číslo \mathit{e} a parametry $x_1, ..., x_n$ a vrátí to samé, co by vrátila \mathit{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 \mathbbm{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 '\mathit{univerzální funkce pro ČRF }k\mathit{-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.

\subsection{Co znamená predikát T?}

Kleeneho predikát $T_1(e, x, y)$ platí, právě když $y=<y_0,y_1>$ (dvojice zakódovaná jako jedno číslo) a \mathit{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 $<y_0,y_1>$ 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$.)

\subsection{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 \mathit{e}-tého programu (\mathit{e}-té ČRFunkce) jedné proměnné spuštěného na vstupu $x$.
Protože to je hodně významná funkce, tzv. \mathit{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 \mathit{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í \mathit{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)$.

\subsection{Co říká s-m-n věta?}

Mám číslo \mathit{e}, tedy \mathit{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 \mathit{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.

\subsection{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. }}
