¿Por qué es la numeración de las funciones computables significativo?

Question

Mi curso es acerca de la teoría de la computabilidad, y estoy teniendo problemas con uno de los principales conceptos. Este puede ser un muy newb pregunta, pero he estado luchando con la comprensión del significado (y yo era lo suficientemente estúpido como para no preguntarle a mi profesor durante la clase).

Alguien puede darme un ejemplo en términos de algo práctico por qué numeración funciones computables es útil?

Soy un estudiante de informática, así que tal vez un ejemplo de ese campo me puede ayudar a entender.

EDIT: Bueno, con la suposición de que la detención problema es la razón fundamental por la que el número de funciones computables.

En ese caso, la numeración de las funciones que debería ayudarnos siempre demostrar que si una función se detendrá o no. Así, si por ejemplo tomamos el gödel numeradas programa $P_{2057}$, lo que significa que el programa S(1), S(1), J(2,1,1). Esto representa la función x+2, sobre el dominio de $\mathbb{N}$.

¿Cómo saber el número 2057 nos ayudan a decidir si este programa se detendrá o no?

EDIT2: he intentado leer los papeles que @sav ligada a mí, aunque me parece relativamente difícil de entender, ya que yo no soy tan buena con los teóricos cosas todavía.

Nuestro libro del curso es la Computabilidad, Una introducción a la función recursiva de la teoría a Nigel Cutland. He encontrado en línea muchas personas alabando a este libro por ser claro y fácil de entender, pero para mí eso no ha sido siempre el caso. Los profesores explicaciones no siempre tiene sentido, y a veces se siente como el libro es el profesor, no a ella(que es una de las grandes razones por las que finalmente me decidí a venir aquí en busca de ayuda).

Por lo tanto, otra pregunta que tengo es, el libro de reclamaciones de la numeración de las funciones a ser de suma importancia en tanto el s-m-n teorema, y la universal de funciones. Después de leer a través de esas partes varias veces, todavía no entiendo su significado, y, sin embargo, constantemente se hace referencia en la parte posterior. Podría alguien tal vez intentar explicar esta conexión de otra manera?

Answer 1

Ya ha sido numeración de las funciones computables, simplemente no lo sabía al principio. La primera vez que vio a una definición de las funciones computables, lo vio en el contexto de algún modelo específico de la computación, tales como el registro de las máquinas. Cada máquina puede ser visto como un "número" de la función que se calcula; por el estándar de codificación de los métodos que realmente puede representar a cada máquina por un número natural, justificando la terminología. (Por ejemplo, tan pronto como usted puede escribir algo en un archivo de texto, usted puede ver el archivo como una secuencia de 0s y 1s. Anteponiendo un 1 da un único número que representa el número de datos que ha escrito).

Por lo que un número no es nada más ni menos que un programa para el cálculo de una función. En lugar de ver el programa como una secuencia de símbolos complejos, se puede ver como una secuencia de 0s y 1s, como un número. Por supuesto, para hacer uso de el programa, usted tiene que saber qué modelo de cálculo en la que fue escrita.

Hay muchos modelos diferentes de cálculo: registro de máquinas, máquinas de Turing, MIENTRAS que los programas, $\lambda$ cálculo, $\mu$-funciones recursivas, etc. Cada uno de estos, cuando está completamente especificado, da una numeración diferente del conjunto de funciones computables.

Un punto clave en la teoría de la computabilidad, que no siempre es evidente en un primer supuesto, es que el principal foco de atención no está en ninguno de estos modelos específicos de cálculo, el enfoque es en las funciones computables a sí mismos.

Así, en lugar de apegándonos a cualquier modelo específico de la computación, que acaba de asumir que tenemos un razonable numeración de las funciones computables, y el trabajo con la numeración de manera abstracta. "Razonable" significa aquí que la numeración tiene propiedades indicadas por el s-m-n teorema, el teorema de recursión, y la universal teorema de la función.

Así, cuando se pregunta por Qué es la numeración de las funciones computables útil?, Me gustaría responder que ya están numeradas. ¿Por qué centrarse en los "números" de manera abstracta? Podríamos llamar a los números de "los programas", y llamar a la numeración de un "sistema de programación". Nada nuevo vendría de que la terminología de cambio.

Es cierto que, si tenemos una numeración de las funciones computables, sabiendo que la función tiene un número 2234 lugar de 2332 en realidad no significa mucho. Algo sorprendente es que el mismo es cierto en todos los estándar de los sistemas de numeración. El undecidability de la detención problema muestra, por ejemplo, que acaba de conocer a un determinado registro de la máquina para calcular una función no es suficiente, en general, para que pueda determinar si la función se detiene en las entradas.

En ciencias de la computación, se diría que se trata de un análisis estático del programa. El undecidability de la detención problema muestra que el análisis estático tiene importantes limitaciones teóricas. Pero esto es cierto en cada razonable sistema de programación, y lo sabemos por el teorema sobre la detención problema es demostrado de manera abstracta, comenzando con un resumen de la numeración de las funciones computables. Podemos probar de una vez por todas, en lugar de demostrar por separado para cada modelo de cálculo.

Answer 2

Yo debería apuntar a Alan Turing del papel

En el documento mencionado, Alan Turing se muestra cómo el diseño de un equipo de propósito general. (Nota histórica: Durante la 2 guerra mundial, Turing construyó equipos que rompería enigma.) Pero esos equipos solo podía hacer una cosa. Ellos no eran de propósito general.

Turing diseños de una máquina que es computacionalmente universal.

Él también muestra que cualquier instrucción que esta máquina realiza pueden ser enumerados por un número.

"Programas" en realidad son números que representan las instrucciones que la máquina de Turing se realiza. Una máquina de propósito general puede leer en cualquier válido programa y ejecutarlo.

Alguien puede darme un ejemplo en términos de algo práctico por qué numeración de las funciones computables es útil

Si usted es un programador, puede haber compilado un programa (tal vez escrito en C o java). Este proceso se lleva a instrucciones escritas en un lenguaje de alto nivel (por ejemplo, C++) y lo convierte en un montón de unos y ceros (es decir: un número binario).

¿Cómo saber el número 2057 nos ayudan a decidir si este programa detener o no?

No, de hecho no hay manera general para determinar si un programa va a detener. Hay muchos programas que pueden ser probadas a detener, pero no en general. Algunos programas podrían simplemente bucle para siempre.

Ver estos videos

Parte 1

Parte 2

Hay lenguajes de programación que sólo se ocupan de un subconjunto de los programas que se detenga. Esto permite demostrar que un programa se detendrá. La pena de esto es que la lengua NO es Turing completo. Creo epigrama es un ejemplo de esto.

Answer 3

Usted debe preguntar a su profesor durante las horas de oficina. Este es un concepto que puede ser importante o no, dependiendo de lo que te interesa y lo será en la prueba. A menudo es usado para demostrar la detención de problema no puede ser resuelto. Después de haber demostrado que, usted puede probar muchos otros problemas no pueden ser resueltos. La prueba sólo muestra que algunos casos de la detención problema no puede ser resuelto. Aún podría ser que todas las instancias que te importa puede ser resuelto.

Answer 4

La numeración es sólo un medio para un fin, y es significativo sólo en el contexto de la prueba en la que se utiliza.

Considere un ejemplo análogo. Supongamos que tenemos 3 palomas y 2 de los casilleros. Si cada agujero sólo puede tener 1 paloma, de demostrar que siempre habrá al menos 1 paloma no en un agujero. Una respuesta: el número de las palomas 1,2,3 por el orden en que entran en un agujero (excluir la entrada simultánea por simplicidad). Entonces en el momento de la paloma 2 entra, sin agujeros están a la izquierda de las palomas, 3.

La numeración de las palomas sólo ayuda con esta prueba, sin ninguna pretensión a la importancia de la numeración de fuera de la prueba. La numeración de las funciones computables es similar.