{{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 \iff 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_n^j(x_1,..,x_n)$ Image: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)\simeq 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)\simeq f(x_2,...,x_n)$ :: $h(i+1,x_2,...,x_n)\simeq 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 \simeq min\{y|\mathbf{f}(x_1,...,x_n,y)\downarrow =0a\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.