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) ∈ ℕᵏ
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í.
Zavedeme techniku takzvané minimalizace, které umožnuje vytvořit funkci f: ℕⁿ → ℕ z jiné funkce g: ℕⁿ⁺¹ → ℕ kde f(x′) je nejmenší y takové, že:
Zapisujeme ji pak f(x′) = µy[g(x′, y) = 0]
Funkce, které můžeme simulovat na 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í.
Sestaví funkce pro jednotlivé funkce TS a to pro mov
, sym
, state
, cursym
, nexthead
, nextstate
, nexttape
a stoptime
.