====== 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//₂, …, //xn//) ∈ ℕ//ᵏ//
===== 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: πⁿ//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 =====
[[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''.