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?
Respuestas:
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.
fuente
Creo que el problema es bastante simple.
Todos los formalismos interactivos pueden ser simulados por máquinas Turing.
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.
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):
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.
fuente
En términos de computabilidad numérica (es decir, calcular funciones de ), todos los modelos conocidos de computación son equivalentes.N → N
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.
fuente
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:
[1] Turings Titanic Machine de Barry S Cooper CACM Vol 55
fuente
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
fuente
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.
fuente
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 :
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
fuente