Přípustné číslování - Admissible numbering
v teorie vypočítatelnosti, přípustná číslování jsou výčty (číslování ) z množiny částečné vypočítatelné funkce které lze převést do a ze standardní číslování. Tato číslování se také nazývají přijatelné číslování a přijatelné programovací systémy.
Rogersova věta o ekvivalenci ukazuje, že všechny přijatelné programovací systémy jsou si navzájem rovnocenné ve formálním smyslu teorie číslování.
Definice
Formalizace teorie vyčíslitelnosti Kleenem vedla ke konkrétní univerzální částečné vypočítatelné funkci Ψ (E, X) definované pomocí T predikát. Tato funkce je univerzální v tom smyslu, že je částečná vypočítatelná a pro jakoukoli částečnou vypočítatelnou funkci F tady je E takové, že pro všechny X, F(X) = Ψ (E,X), kde rovnost znamená, že obě strany jsou nedefinované nebo jsou obě definovány a jsou si rovny. Je běžné psát ψE(X) pro Ψ (E,X); tedy posloupnost ψ0, ψ1, ... je výčet všech částečných vypočítatelných funkcí. Takové výčty se formálně nazývají vypočítatelné číslování částečných vypočítatelných funkcí.
Libovolné číslování η dílčích funkcí je definováno jako přípustné číslování, pokud:
- Funkce H(E,X) = ηE(X) je částečná vypočítatelná funkce.
- Existuje celkem vypočítatelná funkce F takové, že pro všechny E, ηE = ψF(E).
- Existuje celkem vypočítatelná funkce G takové, že pro všechny E, ψE = ηG(E).
Zde první odrážka vyžaduje, aby číslování bylo vypočítatelné; druhý vyžaduje, aby jakýkoli index pro číslování η mohl být efektivně převeden na index na číslování ψ; a třetí vyžaduje, aby jakýkoli index pro číslování ψ mohl být účinně převeden na index pro číslování η.
Rogersova věta o rovnocennosti
Hartley Rogers, Jr. ukázalo, že číslování η částečných vypočítatelných funkcí je přípustné právě tehdy, když existuje celková vypočítatelná bijekce str takové, že pro všechny ηE = ψstr(E) (Soare 1987: 25).
Viz také
Reference
- Y.L. Ershov (1999), "Theory of numbering", Příručka teorie vypočítatelnosti„E.R. Griffor (ed.), Elsevier, str. 473–506. ISBN 978-0-444-89882-1
- M. Machtey a P. Young (1978), Úvod do obecné teorie algoritmů, Severní Holandsko, 1978. ISBN 0-444-00226-X
- H. Rogers, Jr. (1967), Teorie rekurzivních funkcí a efektivní vypočítatelnost, druhé vydání 1987, MIT Press. ISBN 0-262-68052-1 (brožura), ISBN 0-07-053522-1
- R. Soare (1987), Rekurzivně vyčíslitelné množiny a stupně, Perspectives in Mathematical Logic, Springer-Verlag. ISBN 3-540-15299-7