Godel nummer

Et Godel-nummer er et naturlig tall som tildeles et ord på et formelt språk ved hjelp av en bestemt prosedyre, og som unikt identifiserer dette ordet . En slik prosess kalles Gödelization . Betegnelsene refererer til Kurt Gödel , som var den første som brukte en slik prosedyre for å bevise at han var ufullstendig .

Formell definisjon

La være det ( tellbare ) settet med ord på et formelt språk . En funksjon${\ displaystyle M}$ ${\ displaystyle m}$

${\ displaystyle g \ colon M \ to \ mathbb {N}}$

blir kalt Godelization hvis

• ${\ displaystyle g}$ injiserende og forutsigbar ,
• det antall bilder decidable så vel${\ displaystyle g (M)}$
• som kan beregnes på den definerte inverse funksjonen til .${\ displaystyle g (M)}$${\ displaystyle g}$

${\ displaystyle g (m)}$man kaller deretter Gödel-nummeret på . ${\ displaystyle m}$

eksempel

Anta at ord på det formelle språket som er basert på alfabetet , skal bli gudelisert. Vær her . ${\ displaystyle L}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma = \ {a, b, c \}}$

En mulighet for koding ville være å bare tilordne påfølgende tall til bokstavene først. An a tilsvarer 1, a b til 2 og a c til 3. Nå kan du godisere ved å multiplisere kreftene til de påfølgende primtallene som tilsvarer bokstaven : ${\ displaystyle 2,3,5,7, \ ldots}$

Ordet abccba

• Det en i første omgang har verdien${\ displaystyle 2 ^ {1} = 2}$
• Den andre b har verdien${\ displaystyle 3 ^ {2} = 9}$
• Den tredje c har verdien${\ displaystyle 5 ^ {3} = 125}$
• Den fjerde c har verdien${\ displaystyle 7 ^ {3} = 343}$
• Den femte b har verdien${\ displaystyle 11 ^ {2} = 121}$
• Den en i den sjette stilling har verdien${\ displaystyle 13 ^ {1} = 13}$

Gödel-nummeret for abccba i denne kodingen er${\ displaystyle 2 \ ganger 9 \ ganger 125 \ ganger 343 \ ganger 121 \ ganger 13 = 1, 213, 962, 750}$

Siden det er et uendelig antall primtall, kan ord av hvilken som helst lengde faktisk kodes på denne måten, og på grunn av det unike med primfaktoriseringen kan ordet abccba rekonstrueres fra nummeret 1213962750 . Det er tall som ikke tilsvarer noe ord på språket, for eksempel (ingen første bokstav) eller (alfabetet har ikke et fjerde element). Men i det minste kan disse ugyldige verdiene skilles fra de gyldige på en beregningsbar måte. ${\ displaystyle 3 = 2 ^ {0} \ cdot 3 ^ {1}}$${\ displaystyle 16 = 2 ^ {4}}$${\ displaystyle \ Sigma}$

I tillegg til den som er vist her, finnes det selvfølgelig andre metoder for å utføre en Gödelization. For eksempel kan rekkefølgen av primtall også brukes til å nummerere tegnene i alfabetet. I prinsippet er dette ikke nødvendig, men det gjør det også mulig å kode strukturen til termer (formler).

En metode beskrevet i boken Gödel, Escher, Bach av Douglas Hofstadter , bruker for eksempel et stedsverdisystem med basen 1000, som er veldig tydelig, men formelt vanskeligere å håndtere enn en metode som er basert på hovedmakter som en over. Dette gjelder spesielt kodingene som brukes i IT - for eksempel Unicode- kodinger som UTF-7 , som også kan brukes til å kartlegge spesialtegnene. Disse tilordner en sekvens med heksadesimale eller binære sifre til en tegnstreng , som kan forstås som et Gödel-tall som en helhet (nullbyten betyr vanligvis slutten på representasjonsstrengen, så det skal ikke være noen unike problemer på grunn av ledende nuller - ellers er en binær 1 foran). Rekonstruksjonen av tegnstrengen fra denne numeriske representasjonen er gitt på grunn av den nødvendige tekniske funksjonaliteten.

Godelisering av tallteoretiske utsagn

Uttalelser av tallteori (eller andre matematiske teori) kan formuleres ved bruk av en endelig alfabet der elementene (omtrent neste tegn variabler, visse matematiske og logiske symboler , , , , , ) omfatter. (Det utallige uendelige antallet variabler kan representeres som spesielle markerte ord i det endelige alfabetet.) ${\ displaystyle +}$${\ displaystyle \ cdot}$${\ displaystyle =}$${\ displaystyle \ land}$${\ displaystyle \ Rightarrow}$${\ displaystyle \ forall}$

På denne måten kan tallteoretiske utsagn (og til og med bevis) oversettes til tall. Som en konsekvens av dette kan tallteori, som skal håndtere utsagn om tall, også håndtere utsagn om tallteoretiske utsagn og bevis. Dette faktum er det punktet hvor Godels ufullstendighetssetning begynner.

Gödelisering av Turing-maskiner

En kjent anvendelse av Gödel-nummeret er kodingen av en Turing-maskin ved hjelp av et binært ord . På denne måten tildeles hver Turing-maskin et nummer (dvs. settet til alle Turing-maskiner kan telles). Dette faktum utnyttes blant annet i holdeproblemet . ${\ displaystyle w}$

eksempel

Selvfølgelig kan forskjellige konvensjoner for nummereringen avtales. Følgende er et enkelt eksempel på prosessen. Være

${\ displaystyle M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, \ kvadrat, F)}$

en Turing-maskin. Vær o. B. d. A. antall stater så vel som båndalfabetet nummerert fortløpende. ${\ displaystyle Q}$${\ displaystyle \ Gamma}$

${\ displaystyle Q = \ {q_ {0}, q_ {1}, \ ldots, q_ {k} \}, \ Gamma = \ {a_ {0}, a_ {1}, \ ldots, a_ {l} \ }; k, l \ in \ mathbb {N}}$

Vi koder nå foreløpig hver overgang med et ord over alfabetet . Stater eller terminalsymboler er representert ved binær representasjon av deres indekser, de enkelte elementene er også atskilt. ${\ displaystyle \ delta (q_ {m}, a_ {n}) = (q_ {m '}, a_ {n'}, b)}$${\ displaystyle b \ in \ {L, N, R \}}$${\ displaystyle \ {0,1, \ # \}}$${\ displaystyle \ #}$

${\ displaystyle \ delta (q_ {m}, a_ {n}) = (q_ {m '}, a_ {n'}, b) \ mapsto \ # \ # \ operatorname {bin} (m) \ # \ operatorname {bin} (n) \ # \ operatorname {bin} (m ') \ # \ operatorname {bin} (n') \ # \ operatorname {bin} (b)}$

hvor representerer hodebevegelse ( ). For å kunne begrense oss til det tosifrede alfabetet , introduserer vi en kartlegging av settet til : ${\ displaystyle b}$${\ displaystyle L = 0, N = 1, R = 2}$${\ displaystyle \ {0.1 \}}$${\ displaystyle \ {0,1, \ # \}}$${\ displaystyle \ {0.1 \}}$

${\ displaystyle 0 \ mapsto 00,1 \ mapsto 01, \ # \ mapsto 10}$.

Turing-maskinen med den eneste produksjonen blir slik . ${\ displaystyle \ delta (q_ {0}, 0) \ mapsto (q_ {0}, 0, N)}$${\ displaystyle 1010001000100010001001_ {2} = 2656393_ {10}}$

Et alternativ som dispenserer separatoren, bruker det unike ved primærfaktoriseringen for å kunne kode tuplene i et tall.

Se også

• Church-Turing-avhandling

Individuelle bevis

1. ↑ Hans Hermes: Enumerability - Decidability - Calculability , 2. utgave. Springer, Berlin 1971; P. 4, ISBN 3-540-05334-4 , ISBN 0-387-05334-4 .
2. ↑ Vera Spillner: Hvorfor Gödel's ufullstendighetsteorem fremdeles er en redsel for matematikere i dag , på: Spektrum.de av 2. juli 2017, brev til redaktør nr.3