¿Es la interacción más poderosa que los algoritmos?

17

Escuché que la interacción del lema es más poderosa que los algoritmos de Peter Wegner . La base de la idea es que una máquina de Turing (clásica) no puede manejar la interacción, es decir, la comunicación (entrada / salida) con el mundo exterior / entorno.

¿Cómo puede ser esto así? ¿Cómo puede algo ser más poderoso que una máquina de Turing? ¿Cuál es la esencia de esta historia? ¿Por qué no es más conocido?

Dave Clarke
fuente
1
¿Tiene una referencia para incluir en su pregunta? Conozco la definición formal de una máquina de Turing, pero no sé exactamente qué quieres decir con "interacción".
Janoma
Además, parece que "no se puede manejar la interacción con el entorno" es similar a "no se puede manejar la aleatoriedad verdadera", lo que podría ser cierto, pero ambos se pueden aproximar bastante bien con sensores y pseudoaleatoriedad. Pero ese es un comentario mal informado, sin conocer una definición de interacción.
Janoma
2
Las máquinas de Turing no tienen sensores.
Dave Clarke
1
Soy consciente de eso. Y, sin embargo, los ordenadores hacen sensores de uso, que son una forma particular de hacer pasar una entrada a una máquina de Turing. Por lo tanto, los TM interactúan de alguna manera con señales / entornos externos.
Janoma
2
La pregunta no es sobre computadoras. La única interacción con un TM es que el entorno le proporciona una entrada al principio y recibe como máximo una salida al final. Esta no es una interacción general.
Dave Clarke

Respuestas:

11

Las máquinas de Turing pueden manejar la interacción perfectamente, utilizando cintas oracle. Funciona de la siguiente manera: desde el punto de vista de una computadora que maneja la interacción, la entrada del operador es simplemente otra secuencia de bits que envía de vez en cuando a la computadora. Todos sabemos que un administrador de sistemas perezoso podría escribir una secuencia de comandos para enviar la entrada al programa cuando se solicite, de modo que el administrador de sistemas pueda interrumpir antes. La máquina de interacción no tiene forma de saber si realmente hay un operador en vivo en la consola, o si la entrada se canaliza desde otro programa.

Tener todas las entradas de interacción preparadas con anticipación es lo mismo, en términos teóricos, que tener todas las entradas en una cinta separada que es utilizada por una máquina Oracle Turing. Cada vez que la computadora normalmente solicita la interacción del operador, la máquina lee la cinta de entrada. Si la cosa leída de la cinta parece inválida de alguna manera, la máquina de Turing hace exactamente lo que la máquina de interacción haría al recibir esa entrada.

Supongo que Wagner es consciente de la capacidad de usar cintas de oráculo para codificar la entrada, por lo que debe tomar sus comentarios con un grano de sal, o debe preguntar qué quiere decir realmente. Creo que las personas que piensan en la interacción generalmente están preocupadas por dos cosas:

  • Las computadoras "reales" tienen interacción, pero los algoritmos definidos por Turing no. Podemos solucionar esto codificando la entrada en las cintas de oráculo, pero esto aún no coincide con la forma en que operan las computadoras reales. Puede ser bueno estudiar modelos de computación que estén más estrechamente alineados con las computadoras reales.

  • Los algoritmos basados ​​en Oracle a menudo no se consideran en la informática diaria porque las computadoras normales no vienen con un "oráculo" mágico para suministrar datos. Pero podríamos ser capaces de utilizar a una persona como el oráculo. Si la persona entiende los datos que se solicitan, incluso puede ayudar al algoritmo, mejorando así su rendimiento. En otras palabras, un humano puede proporcionar una cinta oracle útil en lugar de simplemente una aleatoria, y en principio esto podría conducir a métodos informáticos más rápidos o más potentes en comparación con los que no están basados ​​en Oracle. Algo similar sucede con la computación aleatoria, después de todo, donde la máquina recibe una secuencia de bits aleatorios como entrada adicional.

Carl Mummert
fuente
Las cintas de Oracle no modelan correctamente la interacción. Considere intentar probar que un sistema informático no filtra información privada. Esto no se puede formalizar en términos de una TM con una cinta de oráculo fija, porque la propiedad depende de caracterizar el cálculo que puede hacer el entorno, exactamente lo que extraemos con una cinta de oráculo.
Neel Krishnaswami
Depende de lo que quiere decir con "modelo correcto". Algunos documentos (por ejemplo, de la comunidad de hipercomputación) parecen sugerir que la interacción de alguna manera amplía el conjunto de funciones computables. Lo que hace, exactamente de la misma manera que lo hace el cálculo de Oracle. Por supuesto, no puede usar TMs para estudiar las propiedades del entorno de computación real; Si desea saber si el procesador de su computadora tiene errores, no ayudará ignorarlo por completo y solo mirar las máquinas de Turing. Pero para las preguntas que solo se refieren a la función que se está calculando, la interacción y los oráculos son equivalentes.
Carl Mummert
nn
Para un trabajo exhaustivo de esta analogía, ver Peter Hancock, Pierre Hyvernat: interfaces de programación y topología básica. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.919
Neel Krishnaswami
1
norte
8

Cálculo del modelo de Turning Machines, y no tiene un concepto de interacción. En ese sentido, una máquina que admite la interacción con un sistema externo puede hacer cosas que una máquina de torneado no puede hacer. Pero el cálculo realizado entre el bit de entrada de una fuente externa obviamente siempre puede ser modelado por una máquina de Turing, por lo que incluso una "máquina de E / S" no puede hacer nada con la entrada externa que una máquina de Turing no podría hacer.

En cierto sentido, una máquina de este tipo puede "decidir" problemas que Turing Machines no puede determinar, pero solo si imagina que el sistema con el que está interactuando tiene poderes de supermáquina de Turing y es confiable (de alguna manera; confiabilidad probabilística seria suficiente).

Imagine un programa para una máquina IO como: "para cualquier entrada de cinta inicial, imprima el contenido de la cinta, luego lea un símbolo desde la entrada externa; acepte si el símbolo es 1 y rechace lo contrario". Este programa puede decidir cualquier problema. Pero solo si el sistema externo con el que puede interactuar es capaz de decidir el problema; Para mí, esa no es una forma muy interesante de decir que IO Machine es capaz de decidir problemas que Turing Machines no puede resolver.

Creo que siempre sería posible representar un cálculo interactivo imaginando una máquina que toma como entrada en su cinta una codificación de alguna configuración anterior junto con una entrada externa, y hace que la máquina se detenga con su cinta que contiene una codificación de una configuración juntos con salida Luego, el proceso de "ejecutar un programa" es ejecutar repetidamente esta máquina de Turing de forma mecánica, con la única parte "no mecánica", sin embargo, la fuente externa se obtiene. Estoy seguro de que podría probar que si un sistema de este tipo obtiene su entrada dando su salida a otra máquina de Turingconfigurado para operar de manera similar, entonces el sistema combinado tiene poderes computacionales idénticos a una sola máquina de Turing. Me parece un argumento convincente de que la computación interactiva no es más poderosa que la computación no interactiva, a menos que el sistema con el que interactúa la computación sea más poderoso que una máquina de Turing .


Sin embargo, hay un sentido no teórico en el que la interactividad puede aumentar la capacidad de una computadora para resolver problemas. Hay muchas cosas que los humanos hacen con mucha precisión que no sabemos cómo hacer que las computadoras funcionen muy bien. Pero también hay muchas cosas por las que los humanos son basura y que podemos hacer que las computadoras hagan. La combinación de estos dos puede llevar a proyectos como reCaptcha , que efectivamente digitaliza libros automáticamente al resolver los problemas de reconocer palabras a humanos en casos difíciles. El sistema resultante de computadora + trabajo humano logra un resultado que actualmente no es práctico lograr ya sea con el cómputo solo o con el trabajo humano solo.

Ben
fuente
8

Recientemente ACM celebró el simposio Ubiquity ' ¿Qué es la computación? 'en el que Peter Wegner publicó un artículo que refleja sus puntos de vista sobre la informática interactiva.

Aquí hay dos extractos del artículo de Peter Wegner:

Un nuevo concepto, que falta en las primeras máquinas de Turing, es la "Computación interactiva", que acomoda la interacción con el entorno durante el cálculo.

Las máquinas de interacción pueden realizar formas informáticas más potentes que las máquinas de Turing, y pueden realizar el tipo de pensamiento propuesto por Turing porque la interacción mejora su rendimiento sobre el de las máquinas de Turing.

Sin embargo, Fortnow, que tiene un artículo en el mismo simposio, parece estar en desacuerdo con las opiniones de Wegner y cree que la informática interactiva no ofrece ningún poder adicional sobre las máquinas de Turing.

Para agregar a la mezcla, parece que todavía estamos debatiendo y definiendo la computación. Moshe Vardi tiene un artículo, ¿Qué es un algoritmo ?, Comunicaciones de la ACM, vol. 55, N ° 3, marzo de 2012.

Vardi informa sobre dos nuevas definiciones de algoritmos. El primero es propuesto por Gurevich y el segundo por Moscovakis.

Gurevich argumentó que cada algoritmo se puede definir en términos de una máquina de estado abstracta.

Moscovakis, por el contrario, argumentó que un algoritmo se define en términos de un recursor, que es una descripción recursiva construida sobre operaciones arbitrarias tomadas como primitivas.

Mohammad Al-Turkistany
fuente
6

No creo que los modelos con IO sean "más potentes" que las máquinas de Turing, simplemente modelan cosas diferentes.

En teoría, podría ver IO como un oráculo (¿ruidoso?). Con un oráculo perfecto, puede computar funciones incompatibles de Turing; ¿Pero de dónde sacar el oráculo? Los humanos son la única opción "super-Turing" (si hay alguna) y se sabe que somos muy poco confiables.

Una clase de programas que se ajustan a este modelo son asistentes de prueba interactivos (por ejemplo, Isabelle / HOL , Coq ). Se ocupan de espacios de prueba indecidibles, pero (posiblemente) todas las pruebas se pueden encontrar (y comprobar) con la entrada adecuada del usuario.

Rafael
fuente
Por lo tanto, las máquinas de Turing con oráculos son más poderosas que las máquinas de Turing sin ellas y las máquinas de Turing con oráculos pueden modelar la interacción. Entonces la respuesta parece ser sí.
Dave Clarke
1
@DaveClarke Si consideras oráculos perfectos, sí.
Raphael
2
Creo que una máquina (o programa) sin ayuda (por cualquier forma de oráculo o entrada) podría, en principio, encontrar todas las pruebas. Hay dos problemas: (1, teórico): nunca será capaz de determinar que una declaración no tiene pruebas, y (2, práctico): generar pruebas a ciegas con la esperanza de tropezar con una declaración dada es tan terriblemente ineficiente que nadie quiere intentarlo, por lo que los asistentes de prueba prefieren una búsqueda guiada, abandonando el éxito "asegurado" en caso de que exista una prueba.
Marc van Leeuwen
2
Como señala Ben en su respuesta, la forma correcta de verlo no es "las máquinas de Turing con oráculos son más poderosas"; las máquinas mismas solo están haciendo cosas computables. La forma correcta de verlo es "algunos oráculos no son computables, por lo que a partir de esos oráculos podemos calcular cosas que no podemos calcular sin un oráculo". La fuerza computacional proviene del oráculo, más que de la máquina.
Carl Mummert
Parece que las máquinas de Turing con oráculos son lo más poderoso. ¿Por qué incluso molestarse con nuevas definiciones?
saadtaame