Gödeli numeratsioon
Formaalses arvuteoorias on Gödeli numeratsioon funktsioon, mis omistab mingi formaalse keele igale sümbolile ja valemile unikaalse loomuliku arvu, mida nimetatakse Gödeli arvuks (GN). Seda mõistet kasutas esmakordselt Kurt Gödel oma mittetäielikkuse teoreemi tõestamiseks.
Gödeli numeratsiooni võib tõlgendada kui kodeeringut, kus igale matemaatilise notatsiooni sümbolile on määratud number, ja siis võib naturaalarvude voog kujutada mingit vormi või funktsiooni. Arvutatavate funktsioonide kogumi numeratsiooni saab siis esitada Gödeli arvude vooga (mida nimetatakse ka efektiivseteks arvudeks). Rogersi ekvivalentsusteoreem sätestab kriteeriumid, mille järgi need arvutuslike funktsioonide hulga numeratsioonid on Gödeli numeratsioonid.
Määratlus
Arvestades loendatavat hulka S, on Gödeli numeratsioon injektiivne funktsioon
f : S → N {\displaystyle f:S\to \mathbb {N} } 
kusjuures nii f kui ka f - 1{\displaystyle f^{-1}} 
(f pöördväärtus) on arvutatavad funktsioonid.
Näited
Baasnootatsioon ja stringid
Üks lihtsamaid Gödeli numeratsiooniskeeme on kasutusel iga päev: Vastavus täisarvude ja nende kujutiste vahel sümbolite jadana. Näiteks jada 2 3 vastab teatud reeglite kohaselt arvule kakskümmend kolm. Samamoodi saab kodeerida sümbolite jadasid mõnest N sümbolist koosnevast tähestikust, identifitseerides iga sümboli numbriga vahemikus 0-N ja lugedes jada täisarvu N+1 baaskujulisena.
Küsimused ja vastused
K: Mis on Gödeli numeratsioon?
V: Gödeli numeratsioon on funktsioon, mis omistab igale formaalse keele sümbolile ja valemile unikaalse naturaalarvu, mida nimetatakse Gödeli arvuks (GN).
K: Kes kasutas esimesena Gödeli numeratsiooni mõistet?
V: Kurt Gödel kasutas esimesena Gödeli numeratsiooni kontseptsiooni oma mittetäielikkuse teoreemi tõestamiseks.
K: Kuidas saab Gödeli numeratsiooni tõlgendada?
V: Me võime Gödeli numeratsiooni tõlgendada kui kodeeringut, kus igale matemaatilise notatsiooni sümbolile on määratud number ja naturaalarvude voog võib kujutada mingit vormi või funktsiooni.
K: Kuidas me nimetame Gödeli numeratsiooniga määratud naturaalarvusid?
V: Gödeli numeratsiooniga määratud naturaalarvusid nimetatakse Gödeli numbriteks või efektiivseteks numbriteks.
K: Mida väidab Rogersi ekvivalentsusteoreem?
V: Rogersi ekvivalentsusteoreem sätestab kriteeriumid, mille jaoks need arvutuslike funktsioonide hulga numeratsioonid on Gödeli numeratsioonid.
K: Mida kujutab endast Gödeli arvude voog?
V: Arvutatavate funktsioonide kogumi numeratsiooni saab esitada Gödeli arvude vooga.
K: Miks on Gödeli numeratsioon oluline formaalses arvuteoorias?
V: Gödeli numeratsioon on formaalses arvuteoorias oluline, sest see annab võimaluse esitada matemaatilisi valemeid ja funktsioone naturaalarvudena, mis võimaldab tõestada olulisi teoreeme, nagu näiteks mittetäielikkuse teoreem.
