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₂, …, xn) ∈ ℕᵏ

Primitivně rekurzivní funkce

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

Počáteční funkce

nulová funkce: ξ() = 0

fce následníka: σ(x) = x + 1

fce projekce: πⁿk: ℕn → ℕ (vybírá k-tou složku z n-tice)

Základní funkce vytvořené z počátečních

kombinace f × g:

ℕᵏ → ℕⁿ⁺ᵐ

f × g(x) = (f(x′), g(x′)), x ∈ ℕᵏ

kompozice g ∘ f(x) = g(f(x′)), x ∈ ℕᵏ

primitivní rekurze:

f(x′, 0) = g(x′)

f(x′, y + 1) = h(x′, y, f(x′, y)), x ∈ ℕᵏ

Parcialně neboli rekurzivní funkce

μ-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]

Turingovsky vyčíslitelné funkce

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

Turingovsky vyčíslitelné parciální rekurzivní funkce

Najdeme TS simulující počáteční funkce

Najdeme TS simuljící primitivně rekurzivní funkce

Najdeme TS simlujicí minimalizaci

Funkce pomocí TS

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

TS pomocí funkcí

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