====== Parciální rekurzivní funkce ======
[[wp>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<sub>n</sub>//) ∈ ℕ//ᵏ//

===== Primitivně rekurzivní funkce =====
[[wp>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: πⁿ<sub>//k//</sub>: ℕ<sup>//n//</sup> → ℕ (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 =====
[[wp>μ-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''.