¿Malentendido la tesis de la Iglesia-Turing?

Mi comprensión de la tesis de la Iglesia-Turing es la siguiente:

• Pone un límite a lo que se puede calcular mediante cualquier proceso discreto y finito.
• Aunque sigue siendo una tesis, no un teorema, si se refutara, esto no significaría solo una actualización de nuestros modelos actuales de computación. Sería un resultado de cambio de paradigma para las matemáticas y la física en general.

Sin embargo, muchas discusiones sobre la Filosofía SE (donde suelo pasar el rato) recurren a la posibilidad de un cálculo de "Super-Turing", y los argumentos en la cuestión de la filosofía de la mente a menudo dependen de la proposición de que Church-Turing es solo una tesis y el Hay varias propuestas para la computación o hipercomputación super-Turing.

La fuente más frecuentemente citada para esto es el artículo de la Enciclopedia de Filosofía de Stanford (SEP) sobre la tesis de Church-Turing .

En particular, el artículo tiene una sección titulada "Malentendidos de la tesis" , que establece lo siguiente:

Parece haber surgido un mito con respecto al artículo de Turing de 1936, a saber, que allí dio un tratamiento de los límites del mecanismo y estableció un resultado fundamental en el sentido de que la máquina universal de Turing puede simular el comportamiento de cualquier máquina. El mito ha pasado a la filosofía de la mente, generalmente con un efecto pernicioso.

[...] Turing no demostró que sus máquinas puedan resolver ningún problema que pueda resolverse "mediante instrucciones, reglas o procedimientos explícitamente establecidos", ni demostró que la máquina universal de Turing "pueda calcular cualquier función que cualquier computadora, con cualquier arquitectura, puede computar ". Él demostró que su máquina universal puede calcular cualquier función que cualquier máquina de Turing pueda calcular; y propuso, y presentó argumentos filosóficos avanzados en apoyo de la tesis aquí llamada tesis de Turing. Pero una tesis sobre el alcance de los métodos efectivos, es decir, sobre el alcance de los procedimientos de cierto tipo que un ser humano sin ayuda de la maquinaria es capaz de llevar a cabo, no tiene ninguna implicación sobre el alcance de los procedimientos que las máquinas son capaces de llevar a cabo, incluso máquinas que actúan de acuerdo con "reglas explícitamente establecidas". Entre el repertorio de operaciones atómicas de una máquina puede haber aquellos que ningún ser humano sin la ayuda de la maquinaria puede realizar.

La sección mencionada anteriormente y especialmente los pasajes citados me parecen totalmente erróneos, como si el autor ni siquiera entendiera el concepto de una máquina de Turing o lo que es la tesis de la Iglesia-Turing. Y, sin embargo, el artículo es citado constantemente como fuente por quienes argumentan en contra de la tesis de Church-Turing, no solo en Philosophy SE, sino incluso por filósofos relativamente conocidos como Massimo Pigliucci . Las razones principales por las que el artículo tiene tanto peso es que el SEP se considera una fuente acreditada en la comunidad de filosofía, y los artículos están sujetos a revisión, y que el autor del artículo, Jack Copeland , es un filósofo establecido que ha publicado extensamente. sobre Turing y sobre IA.

Y, sin embargo, tal como lo veo, el artículo está fundamentalmente equivocado en su presentación de la tesis, a pesar de la reputación de la fuente y del autor.

Mis preguntas:

1. ¿Es correcta mi interpretación de la tesis de Church-Turing?

2. ¿Cómo se puede refutar a quienes utilizan la sección "Malentendidos" de ese artículo como justificación de la idea de que la informática más allá del límite de Turing es una perspectiva realista?

3. ¿Los teóricos de la computabilidad convencional toman en serio la hipercomputación o es el equivalente CS de la fusión en frío y el movimiento perpetuo?

Los campos de filosofía y CS aparentemente tienen diferentes definiciones / interpretaciones de la tesis. En CS, creo que es estándar / aceptado definir la tesis de Church-Turing como la "Tesis M" de la sección "Malentendidos" del artículo (bajo la visión estrecha / mundana). Sin embargo, el artículo afirma que esta es una definición incorrecta de Church-Turing. Entonces simplemente no estamos de acuerdo. (Y tratemos de evitar comenzar una discusión con ellos al respecto ... los argumentos sin sentido son su fuerte , después de todo).

El enfoque adoptado por los filósofos es desafortunado, ya que el lego promedio probablemente esté interesado en la tesis de CS Church-Turing, no en la filosofía expuesta en el artículo. Entonces, citarán el artículo mientras piensan que se refiere a nuestra definición práctica / razonable, cuando no es así.

Entonces mis respuestas a sus preguntas específicas:

1. Sí, por lo que puedo decir.

2. Les diría que el artículo se refiere a una definición de filosofía altamente especializada de Church-Turing. Pero independientemente de lo que uno llama la "verdadera" tesis de Church-Turing, la siguiente tesis se cree casi universalmente entre los científicos informáticos: "Cualquier máquina utilizable de computación que pueda construirse en este universo puede ser simulada por una máquina de Turing".

3. Si por hipercomputación quieres decir físicamente posible / realizable, entonces no, no se toma en serio. Pero es interesante estudiar modelos de hipercomputación incluso si no pueden aparecer en el mundo real, y lo hacemos todo el tiempo. Por ejemplo, podemos considerar una máquina de Turing que tiene acceso a un oráculo que resuelve el problema de detención. Este objeto se estudia todo el tiempo en teoría y no es controvertido, pero nadie cree que se pueda construir uno.

El artículo de la Enciclopedia de Filosofía de Stanford parece estar perdiendo un punto muy importante. No había computadoras cuando Turing escribió su artículo de 1936. Creo que ya estaba pensando en ellas, pero para explicar sus teorías al matemático de la calle, que nunca había soñado con máquinas informáticas que tuvieran capacidades más allá de las máquinas de oficina relativamente limitadas construidas por compañías como IBM, tuvo que enmarcarlas en términos de un procedimiento efectivo realizado por un humano.

El documento de Gandy "Tesis de la Iglesia y principios para mecanismos", en el Simposio Kleene (1980) afirma que la tesis de Church-Turing no se aplica a las máquinas. Luego da lo que pretende ser una prueba de ello para una clase muy limitada de máquinas. Entre las cosas que Gandy afirma es que la tesis original de Church-Turing no tuvo en cuenta el paralelismo.

Las máquinas de Gandy no tienen en cuenta la posibilidad de aleatoriedad, de física no mecánica, de acción a distancia, de asincronía, de variables continuas y otras cosas que podrían usarse para construir máquinas físicas reales.

Entonces, ¿la tesis original de Church-Turing pensada por Church o Turing para aplicarse a las máquinas? Andrew Hodges tiene un artículo que considera esta pregunta, en el que cita la revisión de Church del artículo de Turing:

El autor [Turing] propone como criterio que una secuencia infinita de dígitos 0 y 1 sea "computable", que sea posible diseñar una máquina de computación, que ocupe un espacio finito y con partes de trabajo de tamaño finito, que anotará el secuencia a cualquier número deseado de términos si se permite que se ejecute durante un tiempo suficientemente largo. Por conveniencia, se imponen ciertas restricciones adicionales en el carácter de la máquina, pero estas son de una naturaleza que obviamente no causa pérdida de generalidad, en particular, una calculadora humana, provista de lápiz y papel e instrucciones explícitas, puede considerarse como una especie de máquina de Turing.

Así que Church claramente pensó que la tesis de Church-Turing se extendía a las máquinas.

Por otro lado, parece que Church o Turing no han hecho ningún esfuerzo para considerar las ramificaciones de la física cuántica (u otra no elemental) en la computación, por lo que claramente estaban considerando una clase muy limitada de máquinas.

Los pasajes citados son correctos. Destacan la distinción entre la tesis de Church-Turing (una declaración no demostrable sobre la naturaleza de la computación) y la existencia de una máquina universal de Turing (un teorema matemático).

La existencia de la Máquina Universal de Turing era un hecho no trivial en el momento en que Turing escribió su artículo. Hoy en día, se considera trivial, y en el campo de la programación, Universal Turing Machine se llama intérprete , es decir, un programa que puede ejecutar cualquier otro programa escrito en un lenguaje específico.

Lo que dicen correctamente los pasajes citados es que la existencia de intérpretes no puede probar la tesis de Church-Turing.