{{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) 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) ≃ 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.