Gėdelio numeracija
Formaliojoje skaičių teorijoje Gėdelio numeracija yra funkcija, kuri kiekvienam tam tikros formaliosios kalbos simboliui ir formulei priskiria unikalų natūralųjį skaičių, vadinamą Gėdelio skaičiumi (GN). Pirmą kartą šią sąvoką panaudojo Kurtas Gėdelis (Kurt Gödel), įrodinėdamas savo neišbaigtumo teoremą.
Gėdelio numeraciją galima interpretuoti kaip kodavimą, kai kiekvienam matematinės notacijos simboliui priskiriamas skaičius, o natūraliųjų skaičių srautas gali reikšti tam tikrą formą ar funkciją. Apskaičiuojamųjų funkcijų aibės numeraciją galima atvaizduoti Gėdelio skaičių (dar vadinamų efektyviaisiais skaičiais) srautu. Rogerso lygiavertiškumo teoremoje nurodyti kriterijai, pagal kuriuos apskaičiuojamų funkcijų aibės numeracijos yra Gėdelio numeracijos.
Apibrėžimas
Turint skaičiuojamąją aibę S, Gėdelio numeracija yra injekcinė funkcija
f : S → N {\displaystyle f:S\to \mathbb {N} } 
ir f, ir f - 1{\displaystyle f^{-1}} 
(atvirkštinė f funkcija) yra apskaičiuojamos funkcijos.
Pavyzdžiai
Bazinis užrašas ir eilutės
Viena paprasčiausių Gėdelio numeravimo schemų naudojama kiekvieną dieną: Gödelio sistema, kuri atitinka sveikuosius skaičius ir jų atvaizdavimą simbolių eilutėmis. Pavyzdžiui, seka 2 3 pagal tam tikrą taisyklių rinkinį suprantama kaip atitinkanti skaičių dvidešimt trys. Panašiai simbolių eilutės iš tam tikros N simbolių abėcėlės gali būti koduojamos kiekvieną simbolį identifikuojant skaičiumi nuo 0 iki N ir skaitant eilutę kaip sveikojo skaičiaus bazinį N+1 atvaizdavimą.
Klausimai ir atsakymai
Klausimas: Kas yra Gėdelio numeracija?
A: Gėdelio numeracija - tai funkcija, kuri kiekvienam formaliosios kalbos simboliui ir formulei priskiria unikalų natūralųjį skaičių, vadinamą Gėdelio skaičiumi (GN).
K: Kas pirmasis panaudojo Gėdelio numeravimo sąvoką?
A: Kurtas Gödelis pirmasis panaudojo Gödelio numeracijos sąvoką savo neišbaigtumo teoremai įrodyti.
K: Kaip galime interpretuoti Gėdelio numeraciją?
A.: Gödelio numeraciją galime aiškinti kaip kodavimą, kai kiekvienam matematinės notacijos simboliui priskiriamas skaičius, o natūraliųjų skaičių srautas gali reikšti tam tikrą formą ar funkciją.
K: Kaip vadiname natūraliuosius skaičius, priskiriamus pagal Gėdelio numeraciją?
A: Gėdelio numeracija priskirti natūralieji skaičiai vadinami Gėdelio skaičiais arba efektyviaisiais skaičiais.
K: Ką teigia Rogerso lygiavertiškumo teorema?
A: Rogerso lygiavertiškumo teorema nurodo kriterijus, pagal kuriuos apskaičiuojamų funkcijų aibės numeracijos yra Gėdelio numeracijos.
K: Ką vaizduoja Gėdelio skaičių srautas?
A: Apskaičiuojamųjų funkcijų aibės numeracija gali būti išreikšta Gėdelio skaičių srautu.
Klausimas: Kodėl Gėdelio numeracija yra svarbi formaliojoje skaičių teorijoje?
A.: Gėdelio numeracija svarbi formaliajai skaičių teorijai, nes ji suteikia galimybę matematines formules ir funkcijas pateikti kaip natūraliuosius skaičius, o tai leidžia įrodyti tokias svarbias teoremas kaip neišbaigtumo teorema.
