Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:msz:parcialni_rekurzivni_funkce

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

  1. nulová funkce: ξ() = 0
  2. fce následníka: σ(x) = x + 1
  3. fce projekce: πⁿk: ℕn → ℕ (vybírá k-tou složku z n-tice)

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

  1. kombinace f × g:
    1. ℕᵏ → ℕⁿ⁺ᵐ
    2. f × g(x) = (f(x′), g(x′)), x ∈ ℕᵏ
  2. kompozice gf(x) = g(f(x′)), x ∈ ℕᵏ
  3. primitivní rekurze:
    1. f(x′, 0) = g(x′)
    2. 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

  1. Najdeme TS simulující počáteční funkce
  2. Najdeme TS simuljící primitivně rekurzivní funkce
  3. 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.

/var/www/wiki/data/pages/pitel/msz/parcialni_rekurzivni_funkce.txt · Poslední úprava: 03. 07. 2012, 13.53:32 (upraveno mimo DokuWiki)