Válcové číslování - Cylindric numbering

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Válcové číslování“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Říjen 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie vypočítatelnosti A válcové číslování je zvláštní druh číslování poprvé představen Yuri L. Ershov v roce 1973.

Pokud číslování ${ displaystyle nu}$ je redukovatelný na ${ displaystyle mu}$ pak existuje vypočítatelná funkce ${ displaystyle f}$ s ${ displaystyle nu = mu circ f}$. Obvykle ${ displaystyle f}$ není injekční ale pokud ${ displaystyle mu}$ je válcové číslování, vždy můžeme najít injekčního ${ displaystyle f}$.

Definice

Číslování ${ displaystyle nu}$ je nazýván válcovitý -li

${ displaystyle nu equiv _ {1} c ( nu).}$

To je, pokud ano jeden ekvivalent k jeho válcování

Sada ${ displaystyle S}$ je nazýván válcovitý Pokud je to funkce indikátoru

${ displaystyle 1_ {S}: mathbb {N} až {0,1 }}$

je válcové číslování.

Příklady

• každý Gödelovo číslování je válcovitý

Vlastnosti

• válcová číslování jsou idempotentní, ${ displaystyle nu circ nu = nu}$

Reference

• Yu. L. Ershov, „Theorie der Numerierungen I.“ Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).