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

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