pregunta sobre la numeración de Gödel

Question

Tengo una pregunta sobre la numeración de Gödel, es trivial pero me gustaría saber cómo se puede saber la longitud de una expresión a través de su número de Gödel. ¿?

Creo que se puede utilizar una función recursiva pero no estoy seguro de cuál.....

Answer 1

Pero, ¡por supuesto! Al fin y al cabo, lo importante de los números de Gödel es que se pueden descifrar mecánicamente. Así que dado un número de Gödel $g$ en cualquier sistema sensato de codificación, existe un procedimiento eficaz que toma $g$ y escupe la expresión codificada $e$ y luego hay otro procedimiento efectivo que toma $e$ y escupe su longitud $l$ . Así que al juntarlos, obtendrás un cálculo efectivo que toma $g$ y escupe la longitud $l$ de la expresión que codifica (si la hay).

Entonces, por la Tesis de Church de que los procedimientos efectivos computan funciones recursivas, tiene que haber una función recursiva (parcial) $f\colon\mathbb{N} \rightharpoondown \mathbb{N}$ tal que $f(g) = l$ cuando $g$ efectivamente los números una expresión en su sistema de codificación preferido.

Sin embargo, que La función recursiva que sea dependerá de su sistema de codificación. Pero si usas un esquema tradicional de numeración de potencias de números de Gödel, entonces las cosas serán bastante sencillas. $f$ será la función recursiva primitiva que toma un número $g$ y devuelve $l$ cuando el $l$ -es el mayor factor primo de $g$ . Ejercicio: ¡da una definición recursiva primitiva de esa función!