TIN064 ČRF, ORF, PRF

Wiki-skripta pro Vyčíslitelnost I
Obsah
Úvod (náhled do problematiky) Prerekvizity (co je dobré vědět předem) ČRF, ORF, PRF Rekurzivní spočetnost Převeditelnost RSM Generování RSM Imunní a simple množiny Věty o rekurzi Produktivní a kreativní množiny Neoddělitelné množiny Gödelova věta Seznam zkratek

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 Úvod.

Induktivní výstavba funkcí

Funkce budeme konstruovat induktivně: zavedeme si tři základní funkce (nulová, následník, vydělení j-té složky funkce) 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.
Pokud vám to začne připomínat funkcionální programování (nebo dokonce lambda kalkulus), tak si můžete připsat o něco větší (leč stále nevýznamné) plus. Ano, principem je funkcionální programování (ale bez určené implementace).

Pro šťouraly: Ve vyčíslitelnosti se často volně zaměňují termíny základní funkce a schéma základní funkce (podobně jako v logice se zaměňuje axiom a schéma axiomu). Nulová funkce i následník jsou základní funkce. Ale vydělení je schéma, které definuje nekonečně mnoho základních funkcí.

Technická upozornění:

• Pod následujícími definicemi základních funkcí a hlavně operátorů uvádím pro ilustraci i ukázku odpovídajícího programu v pseudokódu. Nezapomeňte, prosím, že je to jen ilustrace, která má usnadnit pochopení příslušné definice. Úhlové závorky (<>) jsem si do pseudokódu vypůjčil z C++ templates v naději, že to tak třeba bude pro někoho čitelnější. Všechny ty pseudokódy jsou ovšem jen můj výmysl, žádné ustálené značení!
• Ve snaze usnadnit čitelnost definic operátorů, rozhodl jsem se značit funkce tučným fontem a proměnné (tedy přirozená čísla) normálním fontem. Vydrželo mi to ale jen pár odstavců, neb jest to opruz, sorry.

Základní funkce

nulová funkce

$ \mathbf{o}(x) = 0 \quad (\forall x) $

function nulova(x) { return 0; }

následník

$ \mathbf{s}(x) = x+1 \quad (\forall x) $

function succ(x) { return x+1; }

vydělení j-té složky

$ \mathbf{I^j_n}(x_1,...,x_n) = x_j \quad (\forall j,n: 1 \le j \le n) $

function selekce<j>($ x_1,...,x_n $) { return $ x_j $; }

Operátory

Všechny tři operátory mají v dolním indexu n, což značí, že výsledná funkce $ \mathbf{h} $ bude funkcí n proměnných.

substituce

$ S^m_n(\mathbf{f},\mathbf{g_1},...,\mathbf{g_m})=\mathbf{h} $, kde
$ \mathbf{h}(x_1,...,x_n) \simeq \mathbf{f}(\mathbf{g_1}(x_1,...,x_n),...,\mathbf{g_m}(x_1,...,x_n)) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce m proměnných a všechny $ \mathbf{g_i} $ jsou funkce n proměnných. Pokud zavedeme konvenci, že $ \vec x = (x_1,...,x_n) $, tak můžeme zjednodušeně psát $ \mathbf{h}(\vec x) \simeq \mathbf{f}(\mathbf{g_1}(\vec x),...,\mathbf{g_m}(\vec x)) $.

operator $ S^m_n $<$ \mathbf{f},\mathbf{g_1},...,\mathbf{g_m} $>($ x_1,...,x_n $){
  return $ \mathbf{f}(\mathbf{g_1} $($ x_1,...,x_n $), ... , $ \mathbf{g_m} $($ x_1,...,x_n $));
}

• Operátor substituce je základní prvek programování (v lib. prog. jazyce, co znám) — jednoduše úlohu, kterou mám řešit, vyřeším pomocí funkcí, které už naprogramoval někdo dřív.

Tato část je neúplná a potřebuje rozšířit. Možno by bolo šikovnejšie demonštrovať (odpríšerniť? :)) operátory pomocou lambda výrazov, aby sa to neplietlo s vyhodnotením funkcie.

Tady je prepis substituce do CSharpu

       /// <summary>
       /// Substitution(N,M)
       /// </summary>
       /// <param name="f">Function of M arguments</param>
       /// <param name="G1ToGm">List of M functions, each receiving the same N arguments </param>
       /// <returns>Function of N arguments</returns>
       public Func<List<int>, int> Substitution(Func<List<int>, int> f, params Func<List<int>, int>[] G1ToGm)
       {
           var M = G1ToGm.Length; 
           Func<List<int>, int> h = (inputList) =>
               {
                   var N = inputList.Count;
                   return f(G1ToGm.Select(g => g(inputList)).ToList());
               };
           return h;
       }

primitivní rekurze

$ R_n(\mathbf{f},\mathbf{g})=\mathbf{h} $, kde
$ \mathbf{h}(0,x_2,...,x_n) \simeq \mathbf{f}(x_2,...,x_n) $
$ \mathbf{h}(i+1,x_2,...,x_n) \simeq \mathbf{g}(i,\mathbf{h}(i,x_2,...,x_n),x_2,...,x_n) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce n-1 proměnných a $ \mathbf{g} $ je funkce n+1 proměnných.

operator $ R_n\! $<$ \mathbf{f},\mathbf{g} $>($ x_1,x_2,...,x_n $){
  pom := $ \mathbf{f} $($ x_2,...,x_n $);
  for i := 1 to $ x_1 $ do
    pom := $ \mathbf{g} $(i-1, pom, $ x_2,...,x_n $);
  return pom;
}

• Je vidět, že operátor primitivní rekurze má sílu for-cyklu.
• Proměnná $ x_1 $ má zvláštní význam — slouží jako čítač.
• Na přednášce se uváděl vysvětlující příklad na primitivní rekurzi pro n=1. Pak h(0)=konstanta a h(i+1)=g(i,h(i)). Malý problém je v tom, že jsme si nedefinovali nulární funkce a f by v tomto případě musela mít n-1=0 proměnných.

minimalizace

$ M_n(\mathbf{f})=\mathbf{h} $, kde
$ \mathbf{h}(x_1,...,x_n)\downarrow = z \iff \big(\mathbf{f}(x_1,...,x_n,z)\downarrow = 0 \And \forall j<z: \mathbf{f}(x_1,...,x_n,j)\downarrow \ne 0\big) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce n+1 proměnných.

operator $ M_n\! $<$ \mathbf{f} $>($ x_1,...,x_n $){
  i:=0;
  while ($ \mathbf{f} $($ x_1,...,x_n $, i) != 0) do i++;
  return i;
}

• Je vidět, že operátor minimalizace má sílu while-cyklu.
• Poslední proměnná ve funkci f (v pseudokódu označená jako i) má zvláštní význam. Snažíme se ji minimalizovat, to jest najít nejmenší i takové, aby f vracela nulu.
• Pokud se jako f předá funkce, která nikdy nevrací nulu, tak operátor minimalizace vytvoří funkci, která nebude nikde definovaná (výše uvedený pseudokód se zacyklí). To se u předchozích operátorů stát nemohlo: pokud dostaly na vstupu totální funkce, vrátily také totální funkci.
• Pokud nechceme zavádět nulární funkce, je nutné definici operátoru minimalizace doplnit o podmínku, že f je funkce alespoň dvou proměnných.
• Místo $ \downarrow = $ (zkratka za konverguje a rovná se) bychom v definici klidně mohli psát jen $ = $. Použití $ \downarrow \ne $ (zkratka za konverguje a nerovná se) je ale důležité, například pokud $ \mathbf{f}(x_1,...,x_n,0)\uparrow $, tak $ \mathbf{h}(x_1,...,x_n) $ také není definováno, i kdyby třeba $ \mathbf{f}(x_1,...,x_n,1)=0 $.

Definice ČRF, ORF, PRF

• Funkce je ČRF (částečně rekurzivní), pokud ji lze získat pomocí uvedených tří základních funkcí a tří operátorů.
• Funkce je ORF (obecně rekurzivní), pokud je ČRF a totální (všude definovaná).
• Funkce je PRF (primitivně rekurzivní), pokud ji lze získat pomocí uvedených tří základních funkcí a operátorů substituce a primitivní rekurze. (Nesmí se tedy použít operátor minimalizace.)

V uvedených definicích chápeme ČRF (resp. ORF a PRF) jako vlastnost. Můžeme se na věc dívat algebraicky a ekvivalentně definovat ČRF (resp. ORF a PRF) jako třídu funkcí, které mají tuto vlastnost:

• ČRF je nejmenší třída funkcí, která obsahuje tři základní funkce a je uzavřená na $ S^m_n, R_n, M_n $.
• ORF je nejmenší třída totálních funkcí, která obsahuje tři základní funkce a je uzavřená na $ S^m_n, R_n, M_n $.
• PRF je nejmenší třída funkcí, která obsahuje tři základní funkce a je uzavřená na $ S^m_n, R_n $.

Poznámky

• Ke každé ČRF (i ORF a PRF) funkci existuje její odvození. Toto odvození lze chápat jako program vyčíslující danou funkci. Například funkce přičtení dvojky má odvození: $ S^1_1(\mathbf{s},\mathbf{s}) $. Je dobré si uvědomit, že jedna funkce může mít více programů. To znamená, že ty programy jsou různé (mají jiný zdroják = odvození), ale dělají to samé. Ve skutečnosti má každá ČRF nekonečně mnoho odvození (čili programů). Například funkci přičtení jedničky můžeme snadno odvodit jako $ \mathbf{s} $, ale můžeme si odvození (uměle) prodloužit: $ S^1_1(\mathbf{s},\mathbf{I^1_1}) $, nebo dokonce $ S^1_1 \big(\mathbf{s},S^1_1(\mathbf{I^1_1},\mathbf{I^1_1})\big) $ atd.
• ČRFunkcí je spočetně mnoho (jak si za chvíli ukážeme), a klidně by se místo třída ČRFcí mohlo říkat množina ČRFcí, protože nejde o třídu vlastní. Jenže vyčíslitelníci jsou zvyklí, že množinou se vždy myslí nějaká podmnožina přirozených čísel, a tak když chtějí mluvit o množině něčeho jiného, tak to radši i nazvou jinak (třída, systém,...). Obdobně pro ORF a PRF, které evidentně tvoří podmnožiny ČRF.
• Pro zápisky z vyčíslitelnosti se mi osvědčila následující konvence. Místo "Nechť f je částečně rekurzivní funkce 3 proměnných" psát $ f \in \mbox{ČRF}_3 $. Na přednášce se sice nepoužívá, ale je to praktické.

Příklady

Z "programování v ČRF" se sice nezkouší, ale přesto doporučuji si následující příklady vyzkoušet odvodit. Člověk pak získá konkrétnější představu o tom, jak je možné s tak příšerným aparátem jako jsou ČRF něco naprogramovat, a to dokonce cokoli, co lze naprogramovat v lib. jiném jazyce.

sčítání

odvození funkce, která sečte dvě čísla

$ R_2(I^1_1,S^1_3(s,I^2_3)) $

  Příklad: $ x_1=2\,\,\, x_2=3 $

  $ h(0,x_2)=I^1_1(x_2)=I^1_1(3)=3 $

  $ h(1,x_2)=s(I^2_3(0,h(0,x_2),x_2))=s(I^2_3(0,3,3))=s(3)=4 $

  $ h(2,x_2)=s(I^2_3(1,h(1,x_2),x_2))=s(I^2_3(1,4,3))=s(4)=5 $

odčítání

Ve vyčíslitelnosti nemáme záporná čísla, a proto si musíme definovat aritmetické mínus (značí se $ \dot- $), které vrátí buď rozdíl, nebo nulu, pokud by rozdíl měl být záporný. Operace $ 1 \dot- x $ se často používá v podstatě ve významu negace $ x $: pokud totiž bereme 0=false a nenula=true, tak je to totéž.

$ S^2_2(R_2(I^1_1,S^1_3(S^2_1(R_2(o,I^1_3),I^1_1,I^1_1),I^2_3)),I^2_2,I^1_2) $

násobení

$ R_2(o, S^2_3( R_2(I^1_1,S^1_3(s,I^2_3)), I^2_3, I^3_3)) $

Příklad výpočtu pro $ x_1=2\,\,\, x_2=3 $ je tentokrát trochu delší.

Ostré inkluze ČRF, ORF, PRF

Platí: $ \mbox{PRF} \subsetneq \mbox{ORF} \subsetneq \mbox{ČRF} $.

neostré inkluze

Je zřejmé, že každá ORF je ČRF a že i každá PRF je ČRF. Základní funkce jsou totální a operátory substituce a primitivní rekurze totálnost zachovávají. PRF tedy musí být totální. Tím jsme dokázali, že $ \mbox{PRF} \subseteq \mbox{ORF} \subseteq \mbox{ČRF} $

ČRF, která není ORF

Chceme najít nějakou netotální ČRF. Zkonstruujeme tedy například funkci f, která není nikde definovaná (tzv. prázdná funkce). K tomu budeme muset zjevně použít operátor minimalizace: f:=M(g), kde g je nějaká funkce, která nikdy nevrací nulu. Nejjednodušší by bylo vzít jako g rovnou následníka, tedy $ f:=M_0(\mathbf{s}) $. Problém je, že jsme si nezavedli nulární funkce (a tou by f byla).

Zvolme tedy $ g:=S^1_2(\mathbf{s},\mathbf{I^2_2}) $, což znamená, že $ g(x,y)=y+1 $ (na první proměnné nezáleží). Pak máme $ f:=M_1(g) $, dohromady tedy $ f:=M_1\big(S^1_2(\mathbf{s},\mathbf{I^2_2})\big). $

ORF, která není PRF

Příkladem takové funkce je Ackermannova funkce nebo univerzální funkce pro třídu PRF.

• Starší verze Ackermannovy funkce

A(0,y,z) = y+z
A(1,0,z) = 0
A(2,0,z) = 1
A(x,0,z) = z; x>2
A(x,y,z) = A(x-1,A(x,y-1,z),z); y>0 & x>0 

Zde dostáváme $ A(0,y,z) = y + z, A(1,y,z) = y*z, A(2,y,z) = z^y, A(3,y,z) = z^{z^{z^{.^{.^{.^z}}}}} $ a dál už si to ani nejde představit :-)

• Novější verze Ackermannovy funkce(pouze dvě proměnné) - z Wikipedie

A(0,n) = n + 1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1)); m>0 && n>0

• Novější verze Ackermannovy funkce(pouze dvě proměnné) - dle přednášky z října 2009

A(0,n) = 1     ; n = 0
         2     ; n = 1
         n + 2 ; n >= 2     
A(m,0) = 1
A(m,n) = A(m-1,A(m,n-1)); m>0 && n>0

Předchozí dvě definice dávají skutečně různou funkci! co se týče důležitých vlastností je ale (snad) identická. Poslední definice prý dává: $ A(0,x) = x + 2 : (x >= 2), A(1,x) = 2x : (x >= 1), A(2,x) = 2^x,... \, $

Tato část je neúplná a potřebuje rozšířit. Nejsem si jistý, že tomu rozumím správně.

Důkaz (resp. myšlenka důkazu), že Ackermannova fce je ORF, ale není PRF:

1. A(x,y) je ORF
   1. A je totální (je jednoznačně definovaná na všech dvojicích přirozených čísel) - indukcí dle $ \omega^2 $
   2. A je efektivně vyčíslitelná - ?? zastaví se program na vstupních datech?? zobrazíme vstupní data na dobré uspořádání (tj. z každé podmnožiny lze vybrat nejmenší prvek) a v průběhu programu klesáme, v dobrém uspořádání neexistuje nekonečný klesající řetězec a tedy program vždy skončí
   3. je A ČRF? (nějaký čachry s minimalizací) - na přednášce 2009/10 byl důkaz odbyt slovy: Snadno naprogramujeme se zásobníkem.
2. A není PRF - nástin důkazu na přednášce podrobněji nebylo
   1. definuje se "strukturální" složitost PR programů (nechť PR programy jsou PR termy - tj. základní fce, substituce, primitivní rekurze)
   2. definuje se hloubka PR-termů - maximální počet do sebe zanořených for-cyklů (operátorů rekurze)
      1. formálně:
      2. $ hl(s) = hl(\sigma) = hl(I_n^d) = 0 $ pro základní fce
      3. $ hl(S_n^m(P, Q_1,...,Q_n)) = max(hl(P),hl(Q_1),...,hl(Q_n)) $ op. substituce (nejsíš se jedná skutečně o syntaktickou strukturu termu a ne o význam - kdyby šlo o skutečný způsob výpočtu, pak by bylo intuitivnější $ max(hl(Q_1) + hl(P),...,hl(Q_n) + hl(P)) \, $)
      4. $ hl(R_n(P,Q)) = max(hl(P),hl(Q) + 1) \, $ prim. rekurze
   3. definuje se třída funkcí $ R_i $ obsahující všechny PRF, pro které existuje odvození hloubky nejvýše $ i $
   4. fce $ g_i $ je z ($ R_i $ \ $ R_{i-1} $) - je na ní potřeba aspoň $ i $ vnořených for-cyklů (s méně to nejde)
   5. sjednocení všech $ R_i $ jsou všechny PRF
   6. teď se na $ A(x,y) $ nahlídne jako na množinu funkcí $ f_x(y) $ a dokáže se, že $ f_x(x) $ není z žádného $ R_i $
   7. $ A(x,y) $ je rostoucí v obou proměnných s výjimkou konečně mnoha bodů (bez dk.)
   8. $ f_{i+1} $ skoro všude majorizuje libovolnou fci z $ R_i $, tj. $ \forall g \in R_i \exists x_0 :\forall x > x_0 : g(x) < f_{i+1}(x) $ (bez dk.)
   9. sporem, nechť $ A(x,x) $ je z PRF, pak je z nějakého $ R_i $, tedy musí být $ A(x,x) < f_{i+1}(x) < f_x(x) $, pro $ x>i+1 $ SPOR

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

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

Důkaz indukcí podle konstrukce ČRF

• Základní f-ce jsou turingovsky vyčíslitelné
• Operátory zachovávají T-vyčíslitelnost:
  • Substituce: Vyčíslím podfunkce g_i (pomocí m pásek), dám to dohromady a vyčíslím na tom f.
  • Primitivní rekurze: Vyhodnotím f a pak y-krát "otočím" g za použití vstupních parametrů, počítadla cyklů a výsledku z predcházejícího výpočtu.
  • Minimalizace: Opakovaně vyčísluji f na vstupních parametrech a zvětšujícím se počítadle cyklů. Když f poprvé vrátí 0 skončím a vrátím hodnotu počítadla.

TS => ČRF

Výpočet TS se dá chápat jako posloupnost konfigurací (obsah pásky, stav řídící jednotky, pozice hlavy). Tyto konfigurace jde zakódovat do kódu, a výpočet TS chápat jako posloupnost těchto kódů. Kódujeme tzv. Postova slova UqsV do $ \mathbb{N} $.

Jeden krok TS představuje lokální změnu v Postově slově a jistě tedy existuje funkce na kódech, která charakterizuje. Tato funkce vlastně obsahuje jenom rozhodovací strom odpovídající přechodové funkci našeho TS a na to nám stačí prostředky PRF (na if podmínku použijeme operátor primitivní rekurze).

Pomocí for cyklu (primitivní rekurze) pak můžeme sestavit funkci $ Comp(x,s) $, která vypočte kód stavu stroje startujíciho ze stavu odpovídajícímu kódu $ x $ po $ s $ krocích. Pak už jen pomocí while cyklu přes to celé nalezneme posloupnost kroků do konečného stavu, tj. $ Comp(x,\mu_s(\textrm{stroj}\;\textrm{je}\;\textrm{za}\;\textrm{s}\;\textrm{kroku}\;\textrm{v}\;\textrm{konfiguraci}\;q_f) $. Formálně by to šlo zapsat tak, že pro každý turingův stroj TS existuje ČRF $ g $ taková, že pro libovolnou konfiguraci $ k $ platí $ kod(TS(k)) \simeq g(kod(k)) $.

Numerace ČRF

Každá ČRF má z definice nějaké své odvození a každé takové odvození lze převést na přirozené číslo (a zpět, tedy převod je injektivní=prostý). Způsobů, jak tento převod počítat je mnoho, například bychom mohli vzít posloupnost ASCII kódů odvození a chápat to jako jedno číslo, nejčastěji se však používá tzv. standardní numerace.

• Převodu se říká numerace a výslednému číslu kód funkce nebo číslo programu a vetšinou ho budeme značit jako $ e $.
• Jen tak na okraj: Podobně jako ČRF, jdou i logické formule (RSP) převádět na čísla, převodu se říká gödelizace a výsledku gödelovo číslo.
• Jedna funkce může mít víc odvození a tedy i víc kódů. Různé funkce mají ale zaručeně různá odvození a tedy i kódy.
• Důsledkem je, že množina ČRF je spočetná.

Standardní numerace

??? jak funguje ???

Gödelova numerace

Gödel původně numeroval logické formule, a to pomocí prvočísel. Formuli rozložil na atomy, každému atomu přiřadil kód a posloupnost atomů vyjádřil stoupající posloupností prvočísel umocněných na kód odpovídajícího atomu. Přiřadíme-li třeba symbolu '8' kód 18 a symbolu '=' kód 2, můžeme potom tvrzení 8=8 reprezentovat jako 2¹⁸×3²×5¹⁸.

Základní věta aritmetiky říká, že lze každé přirozené číslo jednoznačně zfaktorizovat (rozložit) na mocniny prvočísel. To znamená, že z libovolného čísla vyrobíme posloupnost umocněných prvočísel, kterou pak můžeme interpretovat jako logickou formuli.

Nemělo by dát moc práce si rozmyslet, jak místo logických formulí reprezentovat ČRF. To pak tvoří vlastně důkaz tvrzení o normalizaci v následující větě...

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

Není jasné, existuje-li "přímé" kódování takové, kde _každé_ číslo odpovídá nějaké funkci. Možná tato vlastnost není striktně vzato potřeba, objeví se ale brzy nepříjemné otazky jako co s takovým kódem udělá s-m-n věta nebo univerzální funkce (viz níže).

Je ale asi vidět, že můžeme napsat program (PRF), který ověří, je-li nějaká funkce "syntakticky správně" (můžeme si zase představovat, že náš kód odpovídá ASCII zápisu funkce). Tedy můžeme i napsat program, který postupně generuje ASCII-reprezentaci všech validních programů. No a tak si prostě jako "sekundární" kód funkce budeme udržovat pořadí, ve kterém tuto funkci vyrobí náš generátor - bude-li to první funkce, bude to 0, bude-li to 31992. funkce, bude to 31991.

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 (třeba všechny ČRF_k, nebo všechny PRF_k, ...), tedy vyčísluje $ e $-tou takovou funkci.
  Navíc, tato numerace $ e $ jde efektivně získat z odvození ČRF a naopak z $ e $ lze efektivně získat 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):
  Pro každé $ m, n $ existuje PRF m+1 proměnných $ s_{mn} $ prostá a rostoucí ve všech proměnných taková, že $ \forall e, x_i, y_i : \Psi_{m+n}(e, y_1, ..., y_m, x_1, ..., x_n) \simeq \Psi_{n}(s_{mn}(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} $.^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=<y_0,y_1> $ (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 $ <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 $.)

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 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.

(Kdybychom e kódovali prvočísly jako je popsáno výše, je PRFovitost docela vidět, protože k faktorizaci prvočísel minimalizaci nepotřebujeme a zbytek je snad docela snadný.)

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 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.

* ^ ad 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.

Univerzální PRF a ORF

Předchozí věta dokazuje existenci univerzální ČRFunkce pro třídu ČRF. Přirozeně nás může napadnout, zda bychom nemohli najít univerzální PRFunkci pro PRF, popř. univerzální ORFunkci pro ORF. Inu, nemohli.

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

Důkaz provedeme klasicky "diagonalizačním" sporem. Nechť existuje univerzální funkce $ f $ pro třídu PRF jedné proměnné a nechť je $ f $ sama PRF. Zkonstruujeme funkci $ g $ tak, aby $ g(x)=f(x,x)+1 $. Funkce $ g $ je PRF, a proto musí existovat index $ e $ takový, že $ f(e,x)=g(x) $ (protože $ f $ je univerzální funkce pro PRF jedné proměnné). Spor dostaneme, pokud dosadíme za $ x $ index $ e $, tedy $ f(e,e)=g(e)=f(e,e)+1 $.

Dá se ukázat, že tato fce je ORF (technický důkaz, na přednášce přeskočen) a tudíž je to důkaz ostré inkluze PRF v ORF.

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

Důkaz je přesně stejný jako pro PRF. Několik postřehů na závěr:

• Univerzální funkce pro ORF sice existuje, ale je to ČRF, konkrétně to je $ \Psi_k $ z Kleenovy věty.
• Univerzální funkce pro PRF sice existuje, ale je to ORF. Důkaz je technický a na přednášce bylo pouze zmíněno, že to jde.
• $ \Psi_k $ nelze "ztotálnit" (rozšířit do ORF), prostě nelze dodefinovat nějaké hodnoty pro ty vstupy, na kterých diverguje.
• Promyslete si, proč nelze použít stejný důkaz (jako je zde uveden pro neexistenci univerzální PRF pro PRF) pro neexistenci univerzální ČRF (tedy $ \Psi_k $). V kterém kroku to selže?