Numero di Gödel
Nella teoria dei numeri formali una numerazione di Gödel è una funzione che assegna ad ogni simbolo e formula di un linguaggio formale un numero naturale unico chiamato numero di Gödel (GN). Il concetto fu usato per la prima volta da Kurt Gödel per la dimostrazione del suo teorema di incompletezza.
Una numerazione di Gödel può essere interpretata come una codifica in cui un numero è assegnato ad ogni simbolo di una notazione matematica, e un flusso di numeri naturali può quindi rappresentare qualche forma o funzione. Una numerazione dell'insieme delle funzioni calcolabili può quindi essere rappresentata da un flusso di numeri di Gödel (chiamati anche numeri effettivi). Il teorema di equivalenza di Rogers stabilisce i criteri per cui quelle numerazioni dell'insieme delle funzioni calcolabili sono numerazioni di Gödel.
Definizione
Dato un insieme numerabile S, una numerazione di Gödel è una funzione iniettiva
f : S → N {\displaystyle f:S a \mathbb {N} } 
con sia f che f - 1 {displaystyle f^{-1}} 
(l'inverso di f) sono funzioni calcolabili.
Esempi
Notazione base e stringhe
Uno dei più semplici schemi di numerazione di Gödel è usato ogni giorno: La corrispondenza tra i numeri interi e le loro rappresentazioni come stringhe di simboli. Per esempio, la sequenza 2 3 è intesa, da un particolare insieme di regole, come corrispondente al numero ventitré. Allo stesso modo, le stringhe di simboli di un alfabeto di N simboli possono essere codificate identificando ogni simbolo con un numero da 0 a N e leggendo la stringa come la rappresentazione in base N+1 di un numero intero.
Domande e risposte
D: Cos'è una numerazione di Gödel?
R: Una numerazione di Gödel è una funzione che assegna un numero naturale unico ad ogni simbolo e formula di un linguaggio formale, chiamato numero di Gödel (GN).
D: Chi ha utilizzato per primo il concetto di numerazione di Gödel?
R: Kurt Gödel ha utilizzato per la prima volta il concetto di numerazione di Gödel per la dimostrazione del suo teorema di incompletezza.
D: Come possiamo interpretare la numerazione di Gödel?
R: Possiamo interpretare la numerazione di Gödel come una codifica in cui a ogni simbolo di una notazione matematica viene assegnato un numero, e un flusso di numeri naturali può rappresentare una forma o una funzione.
D: Come chiamiamo i numeri naturali assegnati da una numerazione di Gödel?
R: I numeri naturali assegnati da una numerazione di Gödel sono chiamati numeri di Gödel o numeri effettivi.
D: Cosa afferma il teorema di equivalenza di Rogers?
R: Il teorema di equivalenza di Rogers stabilisce i criteri per i quali le numerazioni dell'insieme delle funzioni computabili sono numerazioni di Gödel.
D: Che cosa rappresenta un flusso di numeri di Gödel?
R: Una numerazione dell'insieme delle funzioni computabili può essere rappresentata da un flusso di numeri di Gödel.
D: Perché la numerazione di Gödel è importante nella teoria formale dei numeri?
R: La numerazione di Gödel è importante nella teoria formale dei numeri, in quanto fornisce un modo per rappresentare le formule matematiche e le funzioni come numeri naturali, il che consente di dimostrare teoremi importanti come il teorema di incompletezza.
