Teljes számozás - Complete numbering

A kiszámíthatóság elmélet teljes számozások általánosításai Gödel számozás első bevezetett AI Mal'tsev 1963 Ők vizsgálták, mert számos fontos eredményeket, mint a Kleene a rekurzió tétele és Rice-tétel , amely eredetileg bizonyult a Gödel-számozott készlet kiszámítható függvényt , továbbra is érvényes a teljes számozású tetszőleges halmazok esetében.

Meghatározás

Egy halmaz számozását teljesnek nevezzük (egy elem vonatkozásában ), ha minden részlegesen kiszámítható függvényhez létezik teljes kiszámítható függvény, így (Ershov 1999: 482): ${\ displaystyle \ nu}$${\ displaystyle A}$${\ displaystyle a \ in A}$ ${\ displaystyle f}$ ${\ displaystyle h}$

${\ displaystyle \ nu \ circ h (i) = {\ begin {cases} \ nu \ circ f (i) & {\ mbox {if}} ~ i \ in \ operátornév {dom} (f), \\ a & {\ mbox {egyébként}}. \ end {esetek}}}$

Ershov utal az elem egy , mint egy „speciális” elemet a számozás. A számozást teljesnek nevezzük, ha a gyengébb tulajdonság rendelkezik: ${\ displaystyle \ nu}$

${\ displaystyle \ nu \ circ f (i) = \ nu \ circ h (i) \ qquad i \ in \ operátornév {dom} (f).}$

Példák

• A szingulett készlet bármilyen számozása befejeződött
• A természetes számokon az identitásfüggvény nem teljes
• A Gödel-számozás hiányos

Hivatkozások

• YL Ershov (1999), "A számozás elmélete", a kiszámíthatóság elméletének kézikönyve , ER Griffor (szerk.), Elsevier, 473–506. ISBN   978-0-444-89882-1
• AI Mal'tsev, Készletek teljes számozással . Algebra i Logika , 1963, vol. 2. szám 2, 4–29 (orosz)