TIN 19. Parciální rekurzivní funkce

Card Set Information

Author:
hrbi
ID:
222784
Filename:
TIN 19. Parciální rekurzivní funkce
Updated:
2013-06-15 07:25:21
Tags:
tin
Folders:

Description:
szz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Totální funkce
    • např. plus: N×N → N
    • plus(x, y) = x + y
  2. Striktně parciální funkce
    • např. div: N×N → N
    • div(x, y) = celá část x / y, je-li y ≠ 0
  3. Počáteční funkce
    • nulová funkce: ξ() = 0, zobrazuje prázdnou n-tici
    • funkce následníka: σ(x) = x + 1
    • projekce: πkn: Nn → N; π23(7, 6, 4) = 6; vybírá k-tou složku n-tice; speciální případ π0n = ()
  4. Primitivně rekurzivní funkce
    • kombinace:
    • f: Nk → Nm, g: Nk → Nn, f × g: Nk → Nm+n
    • f × g(x) = (f(x), g(x)), x ∈ Nk
    • π13×π33(4, 12, 8) = (4, 8)
    • kompozice:
    • f: Nk → Nm, g: Nm → Nn, g ◦ f: Nk → Nn
    • g ◦ f(x) = g(f(x)), x ∈ Nk
    • σ ◦ σ ◦ ξ() = 2
    • primitivní rekurze:
    • f: Nk+1 → Nm, g: Nk → Nm, h: Nk+m+1 → Nm
    • f(x, 0) = g(x)
    • f(x, y + 1) = h(x, y, f(x, y)), x ∈ Nk
  5. Plus definované rekurzivně
    • plus: N2 → N
    • plus(x, y) = π11(x)
    • plus(x, y+1) = σ ◦ π33(x, y, plus(x, y))
  6. Třída primitivních rekurzivních funkcí
    obsahuje všechny funkce, které mohou být z počátečních funkcí vytvořeny: kombinací, kompozicí a primitivní rekurzí
  7. Každá primitivní rekurzivní funkce je totální funkcí
    • počáteční funkce jsou totální
    • aplikací kombinace, kompozice a primitivní rekurze na totální funkce dostaneme totální funkce
  8. Funkce mimo primitivně rekurzivní funkce
    Existují funkce, které jsou vyčíslitelné a nejsou primitivně rekurzivními funkcemi. Jsou to všechny striktně parciální funkce (jako div), ale i totální funkce. Taková totální funkce byla prezentována W. Ackermannem (1928) a nazývá se Ackermannova funkce.
  9. Třída totálních vyčíslitelných funkcí se nazývá μ-rekurzivní funkce
  10. Parciálně rekurzivní funkce
    rozšíření třídy vyčíslitelných funkcí za totální vyčíslitelné funkce pomocí minimalizace
  11. Třída parciálně rekurzivních funkcí
    • třída parciálních funkcí, které mohou být vytvořeny z počátečních funkcí aplikací:
    • (a) kombinace
    • (b) kompozice
    • (c) primitivní rekurze
    • (d) minimalizace
  12. Minimalizace
    • technika umožňující vytvořit funkci f: Nn → N z jiné funkce g: Nn+1 → N předpisem, v němž f(x) je nejmenší y takové, že:
    • (1) g(x, y) = 0
    • (2) g(x, z) je definována pro ∀z < y, z ∈ N
    • zapisujeme: f(x) = μy[g(x,y) = 0]
  13. Příklad parciálně rekurzivní funkce
    • hledá y takové, že x + y = 0
    • najde pouze nulu, protože jsme v oboru N0+
  14. Turingovsky vyčíslitelné funkce
    parciální funkce, kterou může počítat nějaký Turingův stroj
  15. Turingovská vyčíslitelnost parciálně rekurzivních funkcí
    • každá parciálně rekurzivní funkce je Turingovsky vyčíslitelná
    • každý výpočetní proces prováděný Turingovým strojem je procesem vyčíslení nějaké parciálně rekurzivní funkce

What would you like to do?

Home > Flashcards > Print Preview