Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- msz:parcialni_rekurzivni_funkce [16. 06. 2012, 15.41:05] – [Základní funkce vytvořené z počátečních ==] pitel
+++ msz:parcialni_rekurzivni_funkce [24. 08. 2026, 15.46:17] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== 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''.

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku