¿Existe realmente una noción universal de computabilidad?

Hace unas semanas, me encontré con esta gran publicación de JDH y me ha estado preocupando desde entonces. El TL; DR para la prueba es que podemos codificar los resultados de cualquier función en los axiomas de una teoría de conjuntos, por lo que simplemente necesitamos una única máquina de Turing capaz de actuar como un "analizador" inteligente que puede extraer la información de los axiomas. y calcule la función deseada: esto lo entiendo (al menos, conceptualmente y algo formalmente).

Sin embargo, lo que me confunde son las implicaciones filosóficas que esto tiene para las concepciones de computabilidad... Creía que había, en cierto sentido, una noción universal de computabilidad (es decir, había problemas que eran o no decidibles), pero esto sugiere que tales nociones dependen del trasfondo teórico de conjuntos para su cálculo; por ejemplo, esta publicación de Scott Aaronson analiza el trabajo de uno de sus estudiantes al mostrar que hay una Máquina de Turing específica cuyo comportamiento es independiente de ZFC (lo que sugiere nuevamente, implícitamente, que el comportamiento es platónico pero que simplemente no podemos probarlo de ninguna manera).

Perdónenme por mi falta de definición en mi pregunta pero: ¿Hay alguna manera de que esto se pueda resolver? ¿Por qué hay problemas aparentemente incomputables (cuya prueba de incomputabilidad a menudo usa pruebas por contradicción aparentemente sin referencia a ningún trasfondo teórico de conjuntos, por ejemplo, el Problema de la Detención) que pueden ser computados por una Máquina de Turing, sin el uso (oficialmente) de un oráculo ? ¿Tiene esto algún impacto en la tesis de Church-Turing, ya que presumiblemente ningún ser humano podría calcular de manera confiable la función Busy Beaver mientras que el algoritmo universal (si se coloca en el universo correcto) sí puede?

Respuestas (1)

Es posible que hayas entendido mal uno de los aspectos clave de esa publicación de Hamkins. Su teorema no dice que toda función sea computable (a pesar del título).

Dice, en cambio, que para cualquier función dada, puede calcularla en algún universo cuidadosamente elegido, es decir, en algún modelo de teoría de conjuntos cuidadosamente elegido. El universo en el que puede calcularlo variará según la función. Hay muchos, muchos, muchos modelos diferentes de teoría de conjuntos, es decir, muchos universos diferentes de teoría de conjuntos (al igual que hay muchos, muchos, muchos modelos diferentes de teoría de grupos, es decir, muchos grupos diferentes). La función que le dieron puede ser computable en algunos modelos y no computable en otros. Todo lo que garantiza el teorema es la existencia de algún modelo en el que la función dada sea computable.

¿No sería útil sustituir el cómputo paralelo en este universo por el cómputo en serie que progresa simultáneamente a través de múltiples universos?
Incluso decir que "puede calcularlo" en algún universo cuidadosamente elegido parece ser peligrosamente sugerente aquí. Lo que esto realmente significa es que hay una determinada oración aritmética que (a) cuando se interpreta en los números enteros reales expresa la afirmación de que la máquina de Turing especificada proporciona tal o cual salida para tal o cual entrada, y (b) la oración pasa a ser cierto sobre el universo cuidadosamente elegido.
Su comentario de "sugerencia peligrosa" es apropiado, gracias. Pero probablemente no pueda hacer justicia a los aspectos más finos de este problema, así que creo que dejaré mi respuesta como está, con la esperanza de que el OP pueda percibir las aguas peligrosas en las que se está metiendo su publicación.
@Lee Mosher: Perdón por preguntar tanto tiempo después de que se hizo esta pregunta, pero ¿podría explicarme cómo afecta esto a cosas como el problema de la detención? ¿Su prueba solo funciona debido a ciertas suposiciones (ocultas/implícitas) que se basan en algún modelo estándar de ZFC o algo así?
@IskyMathews: Realmente no tiene ningún efecto sobre el problema de la detención. Si aplica la construcción a la función de detención, obtiene un universo especial que (a) tiene números enteros no estándar y (b) tiene una máquina de Turing, de modo que el resultado que el universo especial cree que da su máquina de Turing en el número de una máquina de Turing finita estándar que encajará en su mundo, coincidirá si esa máquina termina cuando se ejecuta en su mundo. Esa respuesta puede ser incorrecta sobre la ejecución de la máquina en el mundo especial en sí, y no tiene garantías sobre máquinas con números no estándar.
¿Existe realmente una noción universal de computabilidad?
RespuestasAquíPolítica de privacidad1y, 0v