Gödel'i numeratsioon — definitsioon ja tähendus formaalses arvuteoorias
Gödeli numeratsioon: selge definitsioon ja tähendus formaalses arvuteoorias, Gödeli arvud, mittetäielikkuse teoreem ja seos arvutatavate funktsioonide ning kodeeringutega.
Formaalses arvuteoorias on Gödeli numeratsioon funktsioon, mis omistab mingi formaalse keele igale sümbolile ja igale sümbolite jadale (näiteks valemile või tõestusjärjestusele) unikaalse loomuliku arvu, mida tavaliselt nimetatakse Gödeli arvuks (GN). Seda mõistet kasutas esmakordselt Kurt Gödel oma mittetäielikkuse teoreemi tõestamiseks, sest numeratsioon võimaldab metasüntaktilisi väiteid kodeerida aritmeetilisteks väideteks.
Definitsioon ja tüüpiline konstruktsioon
Lihtsaim kujutlus Gödeli numeratsioonist on, et kõigepealt määratakse igale algse keele sümbolile mingi koodiarv. Seejärel kodeeritakse lõplik sümbolite jada (nt valem) ühte naturaalarvu, näiteks kasutades esimesi algarve ja eksponente: kui a1, a2, ..., an on jada sümbolite koodid, siis
GN(a1 a2 ... an) = 2^{a1} · 3^{a2} · 5^{a3} · ... · p_n^{a_n},
kus p_i tähistab i-ndat algarvu. Sellisel viisil eri jadad saavad erinevad arvu (tingimuslikult, kui koodiarvud on >0), sest algarvude faktorisatsioon on ainulaadne.
On veel teisi kehtivaid kodeerimismeetodeid: näiteks võib kasutada paarimisfunktsioone (Cantori paarimisfunktsioon), arvu refraktsioonilist esitamist mingis aluses või muu efektiivset pöördet võimaldava teisendust. Oluline ei ole üksikmeetod, vaid see, et numeratsioon on efektiivne (arvutatav), sageli valitakse selline, mis on isegi primitiivselt arvutatav, et arutlused sisemiste definitsioonide kohta oleksid lihtsamad.
Gödeli numbrid valemitele ja tõestustele
Gödeli numeratsioon ei omista numbrit ainult üksikutele sümbolitele, vaid läbi järjestuse kodeerimise ka tervele valemile või tõestusele. Näiteks kui sümbolite hulgas on märgid '0', '=', '+', 'S' (järg), sulud ja kvantorid, siis võime anda lihtsa koodimise:
- '(' → 1, ')' → 2, '0' → 3, 'S' → 4, '+' → 5, '=' → 6, '∀' → 7, '∃' → 8, '¬' → 9, '→' → 10, jne.
- Valemi 0=0 Gödeli arv oleks siis näiteks 2^{3}·3^{6}·5^{3} (vastavalt koodidele 3,6,3).
Analüütiliselt on oluline, et olemas on ka numbriline esitus tõestusest (järjestus avaldustest), mis võimaldab rääkida "x on tõestusena esitatud jada" või "x on valemi numbriline kujutus".
Omadused ja teoreetiline tähendus
- Efektiivsus: tavaliselt valitakse Gödeli numeratsioon nii, et vastavad mapid ja kontrollid on arvutatavad (sageli primitiivselt arvutatavad). See võimaldab sisearitmeetikal rääkida meta-omadustest nagu "y on kood, mis vastab kehtivale valemile" või "x kodeerib kehtiva tõestuse valemi y kohta".
- Aritmetiseerimine: tänu numeratsioonile saab metasüntaktilised mõisted (nt valem, provokatsioon, tõend) tõlkida aritmeetilisteks predikaatideks. See on keskne samm Gödeli mittetäielikkuse teoreemi konstruktsioonis: väited süsteemi enda kohta muutuvad süsteemis representeeritavateks aritmeetilisteks lauseteks.
- Mittekonsistentne üksus: Gödeli numeratsioon ei ole ainus võimalik; sama formaalne süsteem võib kasutada lõpmata palju erinevaid numeratsioone. Oluline on vaid see, et valitud numeratsioon on „efektiivne\" (arvutatav) ja sobivaine omadustega.
- Tõestuste ja valemite hulk: kui numeratsioon on efektiivne, muutub provatavate lausetega seotud hulk aritmeetiliseks ehk arvutatavalt esitatavaks — sellest järeldubki, et teatud metaomadused süsteemile on käsitletavad aritmeetiliselt.
Seos Rogersi ekvivalentsusteoreemiga ja arvutatavusega
Artiklis varem mainitud arvutatavate funktsioonide kogumi numeratsioonist: Gödeli numeratsioon annab viisi, kuidas esitada funktsioonide ja partiidena kirjeid naturaalarvude abil. Rogersi ekvivalentsusteoreem (Rogers' equivalence theorem) täpsustab, millised numeratsioonid arvestatavate funktsioonide hulga puhul loetakse ekvivalente — teisisõnu annab tingimused, millele vastavad numeratsioonid on Gödeli-tyypsed ehk üksteisega siduvad läbi kompositsioonide ja efektivsete muundamiste.
Miks see on oluline?
Gödeli numeratsioon on tööriist, mis sidus matemaatilise süntaksi (sümbolid, valemid, tõestused) aritmeetiliste objektidega. Tänu sellele sai Gödel:
- kodeerida väiteid süsteemi enda võimekuse kohta (nt "see süsteem ei tõesta seda lauset");
- näidata, et teatud süsteemide puhul leidub kehtivaid, kuid süsteemi sees mittetõestatavaid väiteid (mittetäielikkuse teoreem);
- raisonaalistada uurimusi selles, millised metaomadused on süsteemi sees esindatavad ja millised mitte.
Lõppmärkus
Kuigi praktikas kasutatakse sageli primaarset (algarvude eksponentidega) kodeerimist, on oluline mõista, et Gödeli numeratsioon on pigem üldine kontseptsioon — igas konkreetses rakenduses valitakse sobiv ja mugav kodeerimisviis. Peamine nõue on, et kodeering oleks efektiivne (arvutatav) ja võimaldaks süntaktiliste omaduste primitiiv- või üldisemat kontrolli, mida arenduslikud ja loogilised argumendid eeldavad.
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.
Otsige