Parciální rekurzivní funkce

Computable function

Funkce, které je možné spočítat v obecném smyslu bez ohledu na výpočetní systém. Existují totální funkce (pokrývají celý obor hodnot) a striktně parciální (nejsou pro některé hodnoty definovány, např div).

I o TS můžeme uvažovat jako o funkcích. Úplný TS je totální funkce, obyčejný TS je parciální funkce (pokud se zacyklí, funkce není definovaná).

x′ = (x₁, x₂, …, x_n) ∈ ℕᵏ

Primitive recursive function

Třída primitivně rekurzivních funkcí obsahuje funkce, které lze sestrojit pomocí počátečních funkcí a kombinace, kompozice a primitivní rekurze. Každá funkce v této třídě je totální.

1. nulová funkce: ξ() = 0
2. fce následníka: σ(x) = x + 1
3. fce projekce: πⁿ_k: ℕⁿ → ℕ (vybírá k-tou složku z n-tice)

1. kombinace f × g:
   1. ℕᵏ → ℕⁿ⁺ᵐ
   2. f × g(x) = (f(x′), g(x′)), x ∈ ℕᵏ
2. kompozice g ∘ f(x) = g(f(x′)), x ∈ ℕᵏ
3. primitivní rekurze:
   1. f(x′, 0) = g(x′)
   2. f(x′, y + 1) = h(x′, y, f(x′, y)), x ∈ ℕᵏ

μ-recursive function

Zavedeme techniku takzvané minimalizace, které umožnuje vytvořit funkci f: ℕⁿ → ℕ z jiné funkce g: ℕⁿ⁺¹ → ℕ kde f(x′) je nejmenší y takové, že:

• y(x′, y) = 0
• y(x′, z) je definována pro ∀z < y, z ∈ ℕ

Zapisujeme ji pak f(x′) = µy[g(x′, y) = 0]

Funkce, které můžeme simulovat na TS.

1. Najdeme TS simulující počáteční funkce
2. Najdeme TS simuljící primitivně rekurzivní funkce
3. Najdeme TS simlujicí minimalizaci

Parametry funkce můžeme hodit na pásku TS a odělit pomocí Δ. Pokud po provedení výpočtu bude na pásce výsledek funkce pro tyto parametry, TS přijme. Pokud není pro dané parametry funkce definována, TS cyklí.

Sestaví funkce pro jednotlivé funkce TS a to pro mov, sym, state, cursym, nexthead, nextstate, nexttape a stoptime.