Autor: th3j0ker
Mail: yo(arroba)alfonsojimenez(punto)com
URL: http://www.alfonsojimenez.com
Los númeración de Gödel tiene como objetivo asignar un único número decodificable que pueda contener todas las posibles sentencias escritas en un lenguaje formal. En un número de Gödel podemos codificar cualquier programa de n instrucciones.
Para entender un poco mejor la composición de un número de Gödel vamos a definir como {pn:n>1} la sucesión de números primos y la función no inyectiva [...]: N' -> N definida por [a1,...,an] = p1a1...pnan. Diremos que [a1, ..., an] es el número de Gödel de la sucesión finita a1, ...,an, siendo an números naturales. Podemos definir un número de Gödel como el producto de sucesivos primos elevados a una potencia an, por lo que la sucesión an contiene los valores de las potencias del número de Gödel. La primera posición de la función [...] corresponde al 2, la segunda al 3, la tercera al 5, la cuarta al 7 y así sucesivamente siguiendo la numeración de los números primos.
Un ejemplo para verlo más claro, si tenemos un número de Gödel P = [4,5,2], es lo mismo que P = 24·35·52 = 972000. Si queremos realizar la operación inversa únicamente tenemos que descomponer un número natural en factores primos, por ejemplo P = 42 es lo mismo que P = 21·31·50·71 = [1,1,0,1].
Sea un programa P, está constituido por una serie de instrucciones In de la siguiente forma: P = (I1,I2,...,In). Definiremos el número de Gödel que codifica al programa P como #(P) = [#(I1),#(I2),...,#(In)] - 1. Las instrucciones las podemos codificar usando de la función par, una función primitiva recursiva <.,.>: N2 -> N que se encuentra definida por <x,y> = 2x · (2y+1) -1. En el caso de la función par, codifica instrucciones escritas en el lenguaje formal GOTO. El lenguaje GOTO es un modelo secuencial y determinista que su sintaxis está compuesta por:
Sea I una instrucción GOTO podemos definir #(I) = <a,<b,c>>. La correspondecia de a, b y c podemos definirlas como los números que nos indican el formato de la instrucción que codifica el natural I:
Por ejemplo, sea I una instrucción GOTO con #(I)=0. Según la definición de función par, para 0=<0,<0,0>> y siguiendo la correspondecia de a, b y c tenemos que #(I)=#(Y<-Y), por lo que I corresponde a la instrucción skip.
De esta forma podemos codificar un programa P en un número de Gödel: #(P) = [#(I1), ..., #(In)].