Problema de computabilidad de enseñanza

22

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.

mcKlane
fuente
10
¿"Cada función que una computadora puede calcular"? Por lo general, recurro a lenguajes de programación, ya que es probable que los estudiantes conozcan uno. También he tratado de "cualquier receta para calcular una función" como una definición intuitiva de algoritmo.
Michaël Cadilhac
55
Un problema es computable si puede resolverse mediante un conjunto finito de reglas que gobiernan la evolución del sistema dinámico discreto en un número finito de pasos.
Mohammad Al-Turkistany
1
Además, puede usar el décimo problema de Hilbert para explicar a los estudiantes por qué no se puede resolver y que la prueba de insolubilidad requiere, entre otras cosas, formalizar la noción de computabilidad en matemáticas.
Mohammad Al-Turkistany
Otra pregunta: la tesis de Church-Turing establece que una máquina Turing puede calcular una función si y solo si puede ser calculada por alguna máquina de cualquier otro modelo de cálculo "razonable y general" [Goldreich, 2008]. Entonces, ¿es concebible una noción de computabilidad independiente del modelo?
MS Dousti

Respuestas:

37

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.

Andrej Bauer
fuente
2
Me gusta mucho este argumento, porque va de lo concreto (el iPhone) a lo abstracto.
Suresh Venkat
2
Aquí hay un rompecabezas interesante: ¿cuáles son los teoremas smn y utm en Haskell?
Andrej Bauer
18
"Hace 75 años no había computadoras alrededor". Esto es simplemente falso. Hace 75 años había MUCHAS computadoras alrededor. Eran humanos, en su mayoría mujeres; tenían títulos avanzados en matemáticas, algunas herramientas de cálculo mecánico rudimentarias (como máquinas de sumar y reglas de cálculo) y mucho, mucho papel. Estas computadoras fueron la columna vertebral del Proyecto Manhattan y del Parque Bletchley durante la Segunda Guerra Mundial (a pesar de la Bomba y el Bombe). Este es el entorno informático que Turing estaba modelando: humanos con lápiz y papel.
Jeff
10
@Jeffe: Vamos, sabes a qué me refería.
Andrej Bauer
8
@JeffE: podemos probar tu hipótesis. Acuda a sus colegas y pídales que dibujen "una computadora con una falda corta". Por favor, informe cuántos dibujó un ser humano.
Andrej Bauer
12

"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.

Peter Boothe
fuente
3
Nitpicking: el teorema de Abel-Ruffini establece que no existe una solución algebraica general , es decir, una solución en radicales, a ecuaciones polinómicas de grado cinco o más. Sin embargo, existen métodos, como el radical Bring , para obtener soluciones en forma cerrada de ecuaciones quínticas.
MS Dousti
Tu curiosidad es realmente correcta. Cuando se habla de computabilidad, desea hablar sobre cosas como "operaciones permitidas", y las soluciones a los polinomios son una de esas cosas que se vuelven más complejas a medida que las observa. Pero para una introducción, creo que las palabras "procedimiento efectivo" y una mención de la fórmula cuadrática son un excelente punto de partida. No son del todo correctos, pero la intuición es bastante correcta, en mi opinión.
Peter Boothe
8

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".

Dave Clarke
fuente
6

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.

Kevin Wortman
fuente
0

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.

Vineet Kumar
fuente
La pregunta es sobre la enseñanza de la computabilidad. Sería bueno si restringe su respuesta al material que responde esa pregunta. Tenga en cuenta que el OP está enseñando a estudiantes universitarios, por lo que las opiniones personales (como sus últimas tres declaraciones) pueden no estar dentro del alcance.
Vijay D