Aplicabilidad de la tesis de Church-Turing a modelos interactivos de computación

38

Paul Wegner y Dina Goldin han publicado durante más de una década documentos y libros argumentando principalmente que la tesis de la Iglesia-Turing a menudo se tergiversa en la comunidad de Teoría del CS y en otros lugares. Es decir, se presenta como que abarca todo el cómputo cuando, de hecho, solo se aplica al cómputo de funciones, que es un subconjunto muy pequeño de todo el cómputo. En cambio, sugieren que deberíamos tratar de modelar la computación interactiva, donde la comunicación con el mundo exterior ocurre durante la computación.

La única crítica que he visto de este trabajo es en el foro Lambda the Ultimate , donde alguien lamentó a estos autores por publicar continuamente lo que obviamente se conoce. Mi pregunta es, ¿hay alguna crítica más en esta línea de pensamiento, y en particular sus Máquinas de Turing Persistentes? Y si no, ¿por qué entonces parece que se estudió muy poco (podría estar equivocado). Por último, ¿cómo se traduce la noción de universalidad en un dominio interactivo?

zenna
fuente
ps: es posible que también desee echar un vistazo a esta pregunta sobre hipercálculo.
Kaveh
66
Aquí hay otra pregunta similar .
Dave Clarke
77
Creo que Andrej y Neel han explicado aquí que la respuesta es negativa para los problemas de cálculo de funciones de tipo superior. Así que, esencialmente, la Tesis de Church-Turing trata sobre problemas de cálculo de funciones numéricas . Las equivalencias habituales entre modelos de cálculo no se mantienen sobre los tipos superiores. (Sin embargo, según tengo entendido, se trata más de los mecanismos de interacción y de cómo se representan los objetos de tipo superior que del poder computacional de los modelos.) (Reposicionando para corregir algunos errores tipográficos)
Kaveh
77
Estoy de acuerdo con Kaveh.
Andrej Bauer el
En realidad, el primer artículo de Wegners en esta línea parece fecharse entre 1996 y 1997, "Por qué la interacción es más importante que los algoritmos" o "El cambio de paradigma de los algoritmos a la interacción". más adelante en el artículo hay referencia a la cueva de Platos, "el tarpit de Turing" (?), Crítica de la razón pura de Kants, la lógica dialéctica de Marx, Descartes, Penrose, Searle. así que tal vez debería verse como limítrofe con lo filosófico y no tanto en la línea de TCS técnico / matemático. sin matemática, sin lemas, pruebas o thms. aunque tal vez sea un poco grandioso, busca sinceramente comprender "el panorama general" de la historia de la tesis de TC, etc. "
vzn

Respuestas:

75

Aquí está mi analogía favorita. Supongamos que pasé una década publicando libros y artículos argumentando que, contrariamente al dogma teórico de la informática, la Tesis de Church-Turing no logra capturar toda la computación, porque las máquinas de Turing no pueden tostar pan . Por lo tanto, necesita mi nuevo modelo revolucionario , la Máquina de Turing mejorada con tostadora (TETM), que permite el pan como una posible entrada e incluye tostarlo como una operación primitiva.

Podrías decir: claro, tengo un "punto", pero es totalmente poco interesante. Nadie afirmó que una máquina Turing podría manejar todas las interacciones posibles con el mundo externo, sin conectarla primero a los periféricos adecuados. Si desea una TM para tostar pan, debe conectarlo a una tostadora; entonces la TM puede manejar fácilmente la lógica interna de la tostadora (¡a menos que esta tostadora en particular requiera resolver el problema de detención o algo así para determinar qué tan dorado debe ser el pan!). Exactamente de la misma manera, si desea que un TM maneje la comunicación interactiva, entonces necesita conectarlo a dispositivos de comunicación adecuados, como Neel discutió en su respuesta. En ninguno de los casos estamos diciendo nada que no hubiera sido obvio para el mismo Turing.

Entonces, diría que la razón por la que no ha habido un "seguimiento" de las diatribas de Wegner y Goldin es que TCS ha sabido modelar la interactividad siempre que sea necesario, y lo ha hecho felizmente desde el comienzo del campo.

Actualización (30/8): un punto relacionado es el siguiente. ¿Alguna vez les da a los críticos la pausa de que, aquí dentro de la Torre de Marfil Elite Church-Turing (ECTIT), los principales temas de investigación de las últimas dos décadas han incluido pruebas interactivas, protocolos criptográficos multiparte, códigos de comunicación interactiva, protocolos asíncronos para enrutamiento , consenso, difusión de rumores, elección de líderes, etc., y el precio de la anarquía en las redes económicas? Si poner la noción de computación de Turing en el centro del campo hace que sea tan difícil discutir la interacción, ¿cómo es que tan pocos de nosotros lo hemos notado?

Otra actualización: para las personas que siguen tocando el tambor sobre los formalismos de nivel superior que son mucho más intuitivos que los TM, y que nadie piensa en términos de TM como un asunto práctico, permítanme hacer una pregunta extremadamente simple. ¿Qué es lo que permite que todos esos lenguajes de alto nivel existan en primer lugar, que garantiza que siempre puedan compilarse en código máquina? ¿Podría ser ... err ... LA TESIS DE LA IGLESIA , la misma que has estado haciendo? Para aclarar, la tesis de la Iglesia de Turing no es la afirmación de que "¡¡GIRANDO MÁQUINAS REGLA !!" Más bien, es la afirmación de que cualquier lenguaje de programación razonable será equivalente en poder expresivo a las máquinas de Turing, y como consecuencia, que bien podría pensar en términos de los idiomas de nivel superior si es más conveniente hacerlo. Esto, por supuesto, fue una nueva visión radical hace 60-75 años.

Actualización final: he creado una publicación de blog para seguir discutiendo esta respuesta.

Scott Aaronson
fuente
8
Hay una diferencia sustancial entre las tostadoras y la interacción: cada modelo de computación tiene algún mecanismo de E / S. Las tostadoras aparecen raramente. Algunos modelos de modelo de cálculo IO ingenuamente: por ejemplo, las máquinas de Turing tratan con IO solo de manera informal. Esto no es problemático cuando se entiende que el cálculo es funcional, es decir, que comienza con una entrada y termina con una salida, como sucede con las máquinas de Turing. Sin embargo, esto ingenuamente se vuelve oneroso cuando desea lidiar con fenómenos concurrentes genuinos, por ejemplo, ¿cuándo son iguales dos cálculos interactivos? (Continúa abajo.)
Martin Berger
12
En caso de que mis puntos de vista aún no sean lo suficientemente claros, debo agregar que encuentro que toda la literatura sobre el "mito de la tesis de la Iglesia-Turing" no es simplemente hechizante, sino (más concretamente) deprimentemente estéril de ideas. Leerlo trae toda la alegría de leer a alguien que dice refutar la física newtoniana, no por algo genial como la mecánica cuántica o la relatividad, sino porque "las leyes de Newton ignoran la fricción" . O escuchar a una niña explicar por qué técnicamente ganó un juego de mesa porque movió las piezas mientras usted se iba al baño.
Scott Aaronson
77
Creo que la cita de Lance Fortnow extraída a continuación en la respuesta de vzn (artículo original aquí: ubiquity.acm.org/article.cfm?id=1921573 ) demuestra que al menos algunas personas sensatas sostienen la tesis "Fuerte". Fortnow afirma que la tesis de CT puede "simplemente expresarse" como "todo lo computable es computable por una máquina de Turing", escribiendo "todo" donde realmente debería haber escrito "cada ". f:NN
Noam Zeilberger
10
¿Cómo podemos debatir sobre una llamada Tesis que lleva el nombre de Turing y la Iglesia, ninguno de los cuales declaró en su propia escritura la tesis, ya que más tarde se interpretó y evolucionó? - Ver también: fórmula de Euler, eliminación gaussiana, algoritmo de Euclides, teorema de Pitágoras.
Jeff el
14
veinte comentarios! Scott logró con éxito una respuesta histórica a una publicación de blog optimizada de Shtetl ...
Sasho Nikolov
35

Creo que el problema es bastante simple.

  1. Todos los formalismos interactivos pueden ser simulados por máquinas Turing.

  2. Los TM son lenguajes inconvenientes para la investigación en computación interactiva (en la mayoría de los casos) porque los temas interesantes se ahogan en el ruido de las codificaciones.

  3. Todos los que trabajan en la matematización de la interacción lo saben.

Déjame explicarte esto con más detalle.

Las máquinas de Turing obviamente pueden modelar todos los modelos interactivos de computación existentes en el siguiente sentido: elija alguna codificación de la sintaxis relevante como cadenas binarias, escriba una TM que tome como entrada dos programas interactivos codificados P, Q (en un modelo elegido de computación interactiva) y devuelve verdadero exactamente cuando hay una reducción de un paso de P a Q en el sistema de reescritura de términos relevante (si su cálculo tiene una relación de transición ternaria, proceda mutatis mutandis). Entonces obtuviste una TM que hace una simulación paso a paso de la computación en el cálculo interactivo. Claramente, el cálculo pi, cálculo ambiental, CCS, CSP, redes de Petri, cálculo pi cronometrado y cualquier otro modelo interactivo de computación que se haya estudiado puede expresarse en este sentido. Esto es lo que las personas quieren decir cuando dicen que la interacción no va más allá de las MT.

N. Krishnaswami se refiere a un segundo enfoque para modelar la interactividad utilizando cintas de oráculo. Este enfoque es diferente de la interpretación de la relación de reducción / transición anterior, porque la noción de TM cambia: pasamos de TM simples a TM con cintas de oráculo. Este enfoque es popular en la teoría de la complejidad y la criptografía, principalmente porque permite a los investigadores en estos campos transferir sus herramientas y resultados del mundo secuencial al concurrente.

El problema con ambos enfoques es que las cuestiones teóricas de concurrencia genuina están oscurecidas. La teoría de concurrencia busca entender la interacción como un fenómeno sui generis. Ambos enfoques a través de TM simplemente reemplazan un formalismo conveniente para expresar un lenguaje de programación interactivo con un formalismo menos conveniente.

En ninguno de los enfoques, los problemas teóricos de concurrencia genuina, es decir, la comunicación y su infraestructura de soporte tienen una representación directa. Están allí, visibles para el ojo entrenado, pero codificados, escondidos en la niebla impenetrable de la complejidad de la codificación. Entonces, ambos enfoques son malos en la matematización de las preocupaciones clave de la computación interactiva. Tomemos, por ejemplo, cuál podría ser la mejor idea en la teoría de los lenguajes de programación en el último medio siglo, la axiomatización de la extrusión del alcance de Milner et al (que es un paso clave en una teoría general de la composicionalidad):

P|(νx)Q  (νx)(P|Q)provided xfv(P)

Cuán bellamente simple es esta idea cuando se expresa en un lenguaje de lenguaje personalizado como el cálculo pi. Hacer esto usando la codificación del cálculo pi en TM probablemente llenará 20 páginas.

En otras palabras, la invención de formalismos explícitos para la interacción ha hecho la siguiente contribución a la informática: la axiomatización directa de las primitivas clave para la comunicación (por ejemplo, operadores de entrada y salida) y los mecanismos de soporte (por ejemplo, generación de nuevos nombres, composición paralela, etc.) . Esta axiomatización se ha convertido en una verdadera tradición de investigación con sus propias conferencias, escuelas y terminología.

Una situación similar se obtiene en las matemáticas: la mayoría de los conceptos podrían escribirse utilizando el lenguaje de la teoría de conjuntos (o la teoría de topos), pero en su mayoría preferimos conceptos de nivel superior como grupos, anillos, espacios topológicos, etc.

Martin Berger
fuente
1
+1 para explicar los sistemas de computación interactiva power wrt del modelo TM (puede simularlos).
Kaveh
3
Si tan solo pudiera votar esto varias veces.
Vijay D
26

En términos de computabilidad numérica (es decir, calcular funciones de ), todos los modelos conocidos de computación son equivalentes.NN

Sin embargo, todavía es cierto que las máquinas de Turing son bastante dolorosas para las propiedades de modelado como la interactividad. La razón es un poco sutil y tiene que ver con el tipo de preguntas que queremos hacer acerca de los cálculos interactivos.

El primer paso habitual en la interacción de modelado con TM es con cintas oráculo. Intuitivamente, puede pensar en la cadena impresa en la cinta oráculo como una "predicción" de la interacción de E / S de la máquina Turing con el entorno. Sin embargo, considere el tipo de preguntas que queremos hacer sobre los programas interactivos: por ejemplo, podríamos querer saber que un programa de computadora no generará sus datos financieros a menos que reciba su nombre de usuario y contraseña como entrada, y además que los programas no se filtren información sobre contraseñas Hablar sobre este tipo de restricción es muy doloroso con las cadenas de oráculo, ya que refleja una restricción temporal y epistémica en el rastro de la interacción, y la definición de cintas de oráculo le pide que proporcione toda la cadena por adelantado.

Sospecho que hacer esto bien es factible, y esencialmente equivale (1) a considerar las cadenas de oráculo no como un conjunto, sino como un espacio topológico cuyos conjuntos abiertos codifican la lógica modal del tiempo y el conocimiento que desea modelar, y (2) garantizar que los teoremas que demuestres son todos continuos con respecto a esta topología, viendo predicados como funciones continuas desde cadenas de oráculo hasta valores de verdad vistos como el espacio de Sierpinski. Debo enfatizar que esto es una suposición , basada en la analogía con la teoría de dominios. Tendrá que resolver los detalles (y probablemente enviarlos a LICS o algo así) para estar seguro.

Como resultado, las personas prefieren modelar la interacción usando cosas como el modelo Dolev-Yao , donde explícitamente modelas la interacción entre las computadoras y el entorno, para que puedas caracterizar explícitamente lo que el atacante sabe. Esto hace que sea mucho más fácil formular lógicas modales apropiadas para razonar sobre la seguridad, ya que el estado del sistema más el estado del entorno están representados explícitamente.

Neel Krishnaswami
fuente
1

leyendo el blog de Lance Fortnows, acabo de encontrar este reciente / agradable / largo artículo de encuesta sobre el tema con muchas perspectivas y referencias [1] (que no se ha citado hasta ahora), incluye la perspectiva de Wegner / Goldin (entre muchos otros). Solo citaré Fortnows excelente / resumen enfático / declaración / afirmación de la línea de partido TCS casi oficial / uniforme / unánime:

"Sin embargo, algunos científicos informáticos intentan argumentar que la tesis [de Church-Turing] no logra capturar algunos aspectos de la computación. Algunos de estos han sido publicados en lugares prestigiosos como Science, Communications of the ACM y ahora como una serie completa de artículos en ACM Ubiquity. Algunas personas ajenas a la informática podrían pensar que existe un debate serio sobre la naturaleza de la computación. No la hay ".

[1] Turings Titanic Machine de Barry S Cooper CACM Vol 55

vzn
fuente
-4

Estoy muy de acuerdo con los comentarios de Aaronson.

No entiendo el trabajo de Milner. (por ejemplo, cálculo pi, que Milner inventó para describir los procesos de comunicación). Es bastante ilegible para mí, como lo son casi todos los documentos sobre matemáticas y lógica, como las teorías de Lambek. No tengo dudas de que las ideas de Lambek son muy buenas, pero me gustaría verlas traducidas a algún tipo de inglés pidgin que pueda leer.

El comentario de Milner me sorprende de que el cálculo lambda está bien para los "procesos secuenciales", pero que se necesita algo más para comunicar los procesos.

Mi punto de vista (tal vez ingenuo) era que no puede ser así, porque el cálculo pi es Turing completo y, por lo tanto, puede convertirse mecánicamente a otra notación completa de Turing, es decir, cálculo lambda. Por lo tanto, la notación de cálculo pi de Milner se puede convertir automáticamente en cálculo lambda.

Parece que he identificado un proyecto: intuitivamente, debería ser posible convertir mecánicamente de un lenguaje completo de Turing a otro. ¿Hay algún algoritmo para hacer esto? Tendré que buscar en Google. Tal vez esto es increíblemente difícil de hacer, y tan difícil como el problema de detención.

Miré ayer en la red y encontré documentos sobre modelos de cálculo lambda. Me sorprendió descubrir que esto parece ser una madriguera de conejo muy profunda.

Richard Mullins

richard mullins
fuente
-7

Aquí está la cosa, una vez que agrega interactividad (pura), la formalidad se va por la ventana. Ya no es un sistema "cerrado". La pregunta entonces es, ¿cuál es la noción de computación una vez que entra la interactividad? Esa respuesta: bueno, o el otro usuario / máquina está sustituyendo parte de su cómputo (que puede ser inscrito por otra máquina de estado más grande) o ya no está en un sistema formalmente definible y ahora está jugando un juego , en cuyo caso no hay aplicación de la tesis de Church-Turing.

TheDoctor
fuente
2
Los modelos interactivos de computación, como los cálculos de procesos, son juegos en el sentido de la semántica del juego .
Martin Berger
1
El comportamiento humano es irrelevante. Lo importante es que los dispositivos interactivos computables actúen de manera algorítmica y mecánica en sus entradas.
Martin Berger
1
@ Mark J, no entiendo lo que estás diciendo. El enfoque interactivo simplemente dice que un dispositivo es computable si reacciona a sus entradas de forma mecánica, utilizando recursos finitos. Sí, si la otra parte de la interacción hace algo loco, como ingresar Omega de Chaitin, entonces el dispositivo mecánico puede hacer algo loco, como calcular el problema de detención. ¿Y qué?
Martin Berger
1
En mi opinión, el CTT no se trata de lo que es físicamente implementable. En cambio, es una prueba cruda que descarta ciertas cosas claramente no implementables: si el CTT dice que algo no es computable, entonces no es físicamente implementable, pero no creo que la implicación inversa se mantenga.
Martin Berger
1
@ Mark J, el requisito "un dispositivo es computable si reacciona a sus entradas de forma mecánica, utilizando recursos finitos" no requiere que las entradas se generen de forma mecánica. Ciertamente, ingresar el Omega de Chaitin no puede generarse mecánicamente.
Martin Berger
-8

hojeando el papel de Wegner, está claro que está siendo un poco melodramático y contrario, pero tiene razón. Podría decirse que el futuro de la informática se centra mucho más significativamente en la robótica , la inteligencia artificial o la minería de datos (de la gran cantidad de "datos grandes" del mundo real) que no parece mencionar mucho por su nombre, pero que alude claramente con su modelo. y estas áreas se centran en gran medida en el universo fuera de las entradas y salidas de un TM.

Históricamente también se llamaba cibernética , inventada / formulada por Weiner. El punto de la robótica es que las entradas y salidas no son meramente digitales y sin significado, lo que se podría concluir mirando una TM; lo son, pero tienen implicaciones / efectos / causas del mundo real, etc., y la máquina forma un circuito de retroalimentación con el entorno.

entonces diría que los TM y la robótica forman una sinergia muy natural o una relación simbiótica, por así decirlo. pero esta no es una afirmación radical y lo que Wegner anuncia con gran fanfarria es, en otras palabras, poco controvertido o novedoso. en otras palabras, Wegner parece haberse erigido en un iconoclasta intelectual o académico en su estilo a propósito ... y entonces, ¿quién es la comunidad TCS para negarle ese marco melodramático? sin embargo, vea [2] para una refutación seria.

El ejemplo de Wegner de conducir un automóvil es muy relevante y se pueden citar otros avances clave recientes en TCS :

  • el desafío de la carrera en carretera de DARPA y también el acercamiento de Google a la tecnología de un automóvil de conducción. [3]
  • el caso de la victoria del ajedrez Big Blue AI sobre Kasparov
  • la reciente victoria del Deep Blue Jeopardy Challenge
  • el rover de Marte cada vez más autónomo
  • un reciente avance anunciado en el reconocimiento de objetos sin supervisión por parte de Google. [4]
  • reconocimiento de voz comercializado

pero es cierto, lo que comenzó hace décadas como una mera teoría con TMs ahora es un fenómeno del mundo real y los segmentos de la comunidad TCS de la torre de marfil podrían estar en cierta resistencia o incluso en la negación de ese hecho y lo asociado, fundamental [cerca de Kuhnian ] transformación y cambio "actualmente en juego". esto es algo irónico porque Turing fue muy aplicado en muchas de sus perspectivas y estudios, como su interés en una prueba de IA operativa (la prueba de Turing), dinámica química, cálculo de resolución de ajedrez, etc. [5].

incluso puedes ver esto en un microcosmos en este sitio en enfrentamientos sobre cómo definir el alcance, y discusiones acaloradas sobre si una etiqueta aparentemente inocua específica llamada aplicación de la teoría es legítima. [7]

y observemos que TCS de hecho está estudiando muchos modelos interactivos de computación y mucha investigación clave se está llevando a cabo en esa área ... particularmente sistemas de prueba interactivos de los cuales todas las clases de computación importantes se pueden definir en términos de. [6]

[1] La tesis de la Iglesia-Turing: rompiendo el mito de Goldin y Wegner

[2] ¿Hay nuevos modelos de computación? una respuesta a Goldin & Wegner por Cockshott & Michaelson

[3] Busca en Google autos sin conductor: 300,000 millas registradas, ni un solo accidente bajo control de computadora, el Atlántico

[4] Reconocimiento de objetos sin supervisión de Google de imágenes de Youtube

[5] Contribuciones de Alan Turings a CS

[6] Paisaje de sistemas de prueba interactivos

[7] Sobre la modificación de nuestro alcance: una propuesta

vzn
fuente
9
Lo que comenzó hace décadas como una simple teoría con TM es ahora un fenómeno del mundo real . Por supuesto, lo sabemos. Lo llamamos "informática".
Jeff el
Una analogía que estaba en el borde de mis pensamientos mientras escribía esto, pero finalmente se descubrió más tarde: creo que la distinción de la biología in vivo frente a la in vitro es relevante. El TM es análogo a este último. otros modelos (emergentes) son análogos a los primeros. =)
vzn
de todos modos, el volumen de 2006 muestra que muchos prestigiosos informáticos están de acuerdo con el nuevo paradigma. observe también el ensayo final de la colección: Lynn Stein, Interacción, Computación y Educación: este volumen en su conjunto documenta un cambio fundamental en la cultura de la computación desde un enfoque en la resolución algorítmica de problemas hasta una perspectiva en la que la interacción juega un papel central . En este capítulo, Stein señala que dicho cambio debe ir acompañado de un cambio correspondiente en la educación en informática, en la `` historia '' fundamental que contamos a nuestros estudiantes en sus cursos introductorios.
vzn
44
@vzn Argumento de la autoridad
Martin Berger