{{theorem
| <math>h</math> je ČRF <math>n</math> proměnných ⇒ <math>h</math> je Turingovsky vyčíslitelná
| ČRF ⇒ TS
}}
:💡 Přesněji, existuje Turingův stroj <math>M_h</math> takový, že pro každou <math>n</math>-tici přirozených čísel <math>x_1, x_2, \dots, x_n</math> platí
:: <math>M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow</math>
:: a platí-li <math>h(x_1, x_2, \dots, x_n)\downarrow=y</math>, potom výpočet Turingova stroje <math>M_h</math> vydá na výstupu řetězec <math>(y)_B</math>.
; Dk (zakladni funkce vycislim; substituci provedu paralelne na nekolika paskach; prim. rekurzi delam pocitadlem cyklu; minimalizaci taky):
: definujeme TS pro základní funkce a operátory pro odvození <math>h</math>:
:* '''Základní fce'''
:** '''nulová funkce''' <math>o(x)=0</math>
:*** ekvivalentní této operaci na TS: smaže celou pásku a zapíše 0
:** '''následník''' <math>s(x)</math>
:*** implementuje přičtení 1 k bin.číslu
:** '''projekce''' <math>I^j_n (x_1,..,x_n)</math> [[Image:projekce.png|right|thumb|450px|příklad '''projekce''' <math>I^j_n (x_1,..,x_n)</math>: TS <math>M_h</math> přeskočí <math>j-1</math> bloků 0 a 1 oddělených # spolu s jejich smazáním. Poté přeskočí <math>j</math>-tý blok, ale nechá jej být. Následně <math>M_h</math> smaže následujících <math>n - j</math> bloků a vrátí se na začátek toho jediného bloku, který zbyl. Čísla <math>j</math> a <math>n</math> jsou součástí stroje <math>M_h</math>, proto je možné je využívat i ve stavu, což usnadňuje počítání toho, kolik bloků je třeba ještě smazat a přeskočit.]]
:*** smaže prvních <math>j-1</math> bloků
:*** přeskočí <math>j</math> (na něj děláme projekci)
:*** smaže zbytek
:*** vrátí se na jediný nesmazaný <math>j</math>
:* '''Operátory'''
:** '''substituce''' <math>S_n^m</math> pomocí '''3 páskového TS <math>M_h</math>:
::: kde: <math>h(x_1,...,x_n) ≃ f(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n))</math>
:::* na 1. pásce je vstup
:::* postupne simulujeme stroje <math>M_{gi}</math> na 2. pásce (vždy jí smažeme a zkopírumeme na ní 1.), výsledky prekopirujeme na konec 3. (💡 oddělovač #)
:::* na 3. pasce pustime stroj <math>M_f</math> (výsledek pak bude na 3. pásce)
::* '''primitivní rekurze''' <math>R_n</math> pomocí '''3 páskového TS <math>M_h</math> (for-cyklus)''':
::: kde: <math>h(0, x_2, ..., x_n) ≃ f(x_2, ..., x_n)</math>
::: <math>h(i+1, x_2, ..., x_n) ≃ g(i, h(i,x_2,...,x_n), x_2,..., x_n)</math>
:::* '''(init-for-cyklu)''':
::::* na 1. pásce je vstup, na 2.pásce 0 (čítač pro for)
::::* na 3. je 1. bez prvního čísla a pak na ní pustíme <math>M_f</math>
:::* '''(for-cyklus)''': dokud je číslo na 2. < číslo na začátku 1. (<math> x_1</math>)
::::* 2.pásku zkopírujem před výsledek na 3. a na konec zkopirujem 1. (bez prvního čísla)
::::* na 3. pasce pustime stroj <math>M_g</math>
:::* výsledek je pak na 3. pásce
::* '''minimalizace''' <math>M_n(\mathbf{f})=\mathbf{h}</math> pomocí '''2 páskového TS <math>M_h</math> (while-cyklus)''':
::: <math>\mathbf{h}(x_1,...,x_n)\downarrow ≃ min \{ y|\mathbf{f}(x_1,...,x_n,y)\downarrow = 0 \quad a \quad \forall z< y: \mathbf{f}(x_1,...,x_n,z)\downarrow \ne 0\}</math>
:::* na 1. pásce je vstup + #0 (čítač pro while)
:::* '''(while-cyklus):''' dokud simulace <math>M_f</math> na 2.pásce nevrátí 0
::::* smaz 2. a nahraj naní 1. pásku s čítačem+1
::::* nasimuluj <math>M_f</math> na 2.
:::* čítač y zapiš na 1.
