Tengo dificultades para enseñar el concepto de funciones computables. Traté de desarrollar la idea de por qué investigadores como Hilbert / Ackermann / Godel / Turing / Church / ... inventaron la noción de 'computabilidad'. Los estudiantes inmediatamente preguntaron: "¿Qué significa la computabilidad?" y no puedo responder a menos que les enseñe máquinas de Turing, y luego respondo "una función es computable si una máquina de Turing la computa".
Asi que,
¿Existe una descripción de computabilidad que no requiera recurrir a máquinas de Turing, cálculo λ o modelos similares de computación? Incluso una descripción intuitiva será suficiente.
Respuestas:
Hace 75 años no había computadoras alrededor. Así que uno tenía que explicar con mucho cuidado la idea matemática de una computadora.
Hoy todos saben lo que es una computadora, y probablemente lleva una alrededor la mayor parte del tiempo. Esto se puede usar con mucho éxito en la enseñanza porque puede omitir la idea bastante anticuada de una máquina con una cinta. Quiero decir, ¿quién usa una cinta? (Lo sé, lo sé, te sientes insultado y Turing fue un gran hombre y todo eso, y estoy de acuerdo contigo).
Simplemente entras en la clase y preguntas: ¿hay algo que tus iPhones no puedan calcular? Esto te lleva inmediatamente a preguntas sobre recursos limitados. Luego dices: bueno, supongamos que tu máquina realmente tiene memoria ilimitada, ¿hay algo que no pueda calcular? E idealiza un poco más y limita la atención a las funciones de teoría de números (porque no está interesado en Facebook en este momento). Tendrás que explicar un poco cómo funcionan las computadoras (como se menciona en los comentarios, es bueno si los estudiantes conocen un lenguaje de programación porque puedes usarlo en lugar de describir el hardware), pero después de eso puedes usar todos los argumentos clásicos de computabilidad teoría para obtener resultados. No importa que la imagen mental de sus alumnos de una máquina sea iPhone. De hecho, importa:más relevante para ellos saber que su iPhone no puede hacer ciertas cosas.
fuente
"Una función es computable si hay un 'procedimiento efectivo' para pasar de entrada a salida". Al presentar este tema, he señalado en el pasado cómo ellos (los estudiantes) tienen un procedimiento efectivo para resolver ecuaciones cuadráticas, pero no tengo uno para resolver ecuaciones de grado 5 o más. Esto puede pasar a una discusión sobre cómo uno podría formalizar un 'procedimiento efectivo', pero esa discusión es algo que desea que suceda, por lo que creo que es una característica, en lugar de un error.
fuente
Quizás el punto es que todos estos modelos tenían como objetivo capturar cuál es la noción de computabilidad. El hecho de que todos ellos sean equivalentes significa que la noción que intentan capturar es sólida. Entonces, aunque esto no escapa a su dilema, esta robustez da crédito a la noción de que "una función es computable si hay una máquina de Turing que la computa".
fuente
Empiezo preguntando "¿hay alguna pregunta que ninguna computadora pueda responder de manera convincente?" y dirigir la discusión hacia preguntas filosóficas como "si un árbol cae en el bosque, ¿hace algún ruido?" o "¿hay una vida futura?" Rápidamente llegamos a un consenso de que el lenguaje humano puede expresar preguntas sí / no que involucran paradojas o conceptos que no pueden expresarse matemáticamente, por lo que sí, hay preguntas no computables.
Luego pregunto retóricamente si hay preguntas no computables sobre conceptos que se pueden representar en una computadora, por ejemplo, enteros y gráficos. Digo que sí, un ejemplo es el famoso problema de detención, que consiste en examinar una descripción de un programa y decir si tiene bucles infinitos. Intuitivamente, resulta que los bucles infinitos son como agujeros negros, y cualquier programa que observe un bucle infinito podría quedar atrapado en un bucle infinito. Por lo tanto, cualquier procedimiento que responda a ese problema puede ejecutarse para siempre, por lo que según la definición de "algoritmo", ningún algoritmo puede responder al problema de detención.
Luego vuelvo a sumergirme en las pruebas en las máquinas de Turing.
fuente
Bueno, una función es computable si acepta entradas formadas o generadas por un patrón específico. Un patrón específico significa que todas las entradas deben tener una relación, una entrada particular puede ser generada por la entrada anterior o siguiente. Si las entradas no tienen este tipo de secuencia, entonces no hay posibilidad de desarrollar un modelo o función que pueda aceptar. Una cosa más que quiero decir es que hay una diferencia básica entre una máquina y un ser humano. No se pudo formar una máquina para entradas no secuenciales, pero los humanos sí. Además, esta es una gran interrupción de la fabricación de robots reales de comportamiento humano.
fuente