Řešené otázky NTIN090/ČRF2TS

Věta ( ČRF ⇒ TS ):  $ h $ je ČRF $ n $ proměnných ⇒ $ h $ je Turingovsky vyčíslitelná

💡 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) $
    

    příklad projekce $ I^j_n (x_1,..,x_n) $: TS $ M_h $ přeskočí $ j-1 $ bloků 0 a 1 oddělených # spolu s jejich smazáním. Poté přeskočí $ j $-tý blok, ale nechá jej být. Následně $ M_h $ smaže následujících $ n - j $ bloků a vrátí se na začátek toho jediného bloku, který zbyl. Čísla $ j $ a $ n $ jsou součástí stroje $ M_h $, 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 $ 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.