Numeracion de godel

Solo disponible en BuenasTareas
  • Páginas : 4 (812 palabras )
  • Descarga(s) : 0
  • Publicado : 30 de agosto de 2012
Leer documento completo
Vista previa del texto
Numeración de Gödel

1

Numeración de Gödel
En teoría de los números un número de Gödel es una función que asigna a cada símbolo y fórmula de un lenguaje formal un número único, denominadoNúmero de Gödel (GN). El concepto fue utilizado por primera vez por Kurt Gödel para la demostración del teorema de Incompletitud de Gödel. La enumeración de un conjunto de funciones computables se denominatambién enumeración de Gödel o enumeración efectiva. Una enumeración de Gödel se puede interpretar como un lenguaje de programación donde los números de Gödel están asignados a cada función computableigual que los programas que cálculos los valores para la función en este lenguaje de programación.

Definición
Dado un conjunto enumerable S, una enumeración de Gödel es una función

donde f yla inversa de f son funciones computables.

Ejemplo
Paso 1
Los números de Gödel se construyen con referencia a símbolos de cálculo proposicional y la aritmética formal. Cada símbolo se asignaprimero a un número natural, por tanto: .
Símbolos lógicos ¬ 1 ("no") 2 ("para todos") 3 ("si, entonces") 4 ("o") 5 ("y") ( ) S 0 = . + Símbolos proposicionales P Q R S Variables individuales 15 18 21 24Números más grandes que 12 con resto 1 cuando se dividen por 3 6 7 8 ("es el sucesor de") 9 10 11 12 Números más grandes que 12 y divisibles por 3 Números 1:12

Numeración de Gödel

2
v x ySímbolos de predicado E F G 13 16 19 Números más grandes que 12 con resto 2 cuando se dividen por 3 14 17 20

Y así para todos los símbolos posibles. La sintaxis del cálculo proposicional asegura que nohay ambigüedad entre el símbolo "P" y el símbolo "+" aunque ambos estén asignados al número 12.

Paso 2
A cada enunciado aritmético se le asigna un número de Gödel único utilizando series denúmeros primos. Se basa básicamente en el siguiente código: 1er primo carácter × 2º primo carácter × 3er primo carácter etc. Por ejemplo el enunciado x, P (x) se convierte en 22 × 316 × 512 × 76 × 1116...
tracking img