{{theorem 
  | $h$ je ČRF $n$ proměnných ⇒ $h$ je Turingovsky vyčíslitelná

  | ČRF ⇒ TS
}} 

:💡 Přesněji, existuje  Turingův stroj $M_h$ takový, že pro každou $n$-tici přirozených čísel  $x_1, x_2, \dots, x_n$ platí  

:: $M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow$ 
:: a platí-li  $h(x_1, x_2, \dots, x_n)\downarrow=y$, potom výpočet Turingova stroje  $M_h$ vydá na výstupu řetězec  $(y)_B$.

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í $h$:
    * **Základní fce**
        * **nulová funkce** $o(x)=0$
            * ekvivalentní této operaci na TS: smaže celou pásku a zapíše 0
        * **následník** $s(x)$
            * implementuje přičtení 1 k bin.číslu
        * **projekce** $I^j_n (x_1,..,x_n)$ ![ kolik bloků je třeba ještě smazat a přeskočit.](Archiv/Řešené otázky NTIN090/ČRF2TS/Projekce.png)
            * smaže prvních $j-1$ bloků
            * přeskočí $j$ (na něj děláme projekci)
            * smaže zbytek
            * vrátí se na jediný nesmazaný $j$
    * **Operátory**
        * **substituce** $S_n^m$ pomocí **3 páskového TS $M_h$: **
        :: kde: $h(x_1,...,x_n) ≃ f(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n))$
            * na 1. pásce je vstup
            * postupne simulujeme stroje $M_{gi}$ 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 $M_f$ (výsledek pak bude na 3. pásce)
        * **primitivní rekurze** $R_n$ pomocí **3 páskového TS $M_h$ (for-cyklus)**:
        :: kde: $h(0, x_2, ..., x_n) ≃ f(x_2, ..., x_n)$ 
        :: $h(i+1, x_2, ..., x_n) ≃ g(i, h(i,x_2,...,x_n), x_2,..., x_n)$            
            * **(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 $M_f$
            * **(for-cyklus)**: dokud je číslo na 2. <číslo na začátku 1. ($ x_1$)
                * 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 $M_g$
            * výsledek je pak na 3. pásce
        * **minimalizace** $M_n(\mathbf{f})=\mathbf{h}$ pomocí **2 páskového TS $M_h$ (while-cyklus)**:
        :: $\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\}$
            * na 1. pásce je vstup + #0 (čítač pro while)
            * **(while-cyklus):** dokud simulace $M_f$ na 2.pásce nevrátí 0
                * smaz 2. a nahraj naní 1. pásku s čítačem+1
                * nasimuluj $M_f$ na 2.
            * čítač y zapiš na 1.