Kompletní číslování - Complete numbering

v teorie vypočítatelnosti kompletní číslování jsou zobecnění Gödelovo číslování poprvé představen A.I. Mal'tsev v roce 1963. Jsou studovány, protože několik důležitých výsledků, jako je Kleenova věta o rekurzi a Riceova věta, které byly původně prokázány pro sadu Gödelů vypočítatelné funkce, stále držte pro libovolné sady s úplným číslováním.

Definice

A číslování ${ displaystyle nu}$ sady ${ displaystyle A}$ je nazýván kompletní (s ohledem na prvek ${ displaystyle a v A}$) pokud pro každého částečná vypočítatelná funkce ${ displaystyle f}$ existuje a celková vypočítatelná funkce ${ displaystyle h}$ takže (Ershov 1999: 482):

${ displaystyle nu circ h (i) = left {{ begin {matrix} nu circ f (i) & { mbox {if}} i in mathrm {dom} (f) , a & { mbox {jinak}}. end {matrix}} vpravo.}$

Ershov odkazuje na prvek A jako „speciální“ prvek pro číslování. Číslování ${ displaystyle nu}$ je nazýván předkompletní pokud platí slabší vlastnost:

${ displaystyle nu circ f (i) = nu circ h (i) qquad i in mathrm {dom} (f). ,}$

Příklady

• Jakékoli číslování a singletonová sada je kompletní
• The funkce identity na přirozených číslech je ne kompletní
• A Gödelovo číslování je předkompletní

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
• A.I. Mal'tsev, Sady s úplným číslováním. Algebra i Logika 1963, sv. 2, č. 2, 4-29 (ruština)