¿Es una máquina de Turing "por definición" la máquina más poderosa?

54

Estoy de acuerdo en que una máquina de Turing puede resolver "todos los posibles problemas matemáticos". Pero eso se debe a que es solo una representación de la máquina de un algoritmo: primero haga esto, luego haga eso, finalmente obtenga eso.

Quiero decir que cualquier cosa que sea solucionable puede ser representada por un algoritmo (porque esa es precisamente la definición de 'solucionable'). Es solo una tautología. No dije nada nuevo aquí.

Y al crear una representación de máquina de un algoritmo, que también resolverá todos los posibles problemas tampoco es nada nuevo. Esto también es mera tautología. Básicamente, cuando se dice que una máquina de Turing es la máquina más poderosa, ¡lo que efectivamente significa es que la máquina más poderosa es la máquina más poderosa!

Definición de "más poderoso": lo que puede aceptar cualquier idioma.
Definición de "Algoritmo": Proceso para hacer cualquier cosa. Representación de máquina de "Algoritmo": una máquina que puede hacer cualquier cosa.

Por lo tanto, es lógico que la representación de la máquina de un algoritmo sea la máquina más poderosa. ¿Qué es lo nuevo que Alan Turing nos dio?

Sounak Bhattacharya
fuente
99
La máquina de torneado no puede resolver el problema de detención. Sin embargo, no hay pruebas de que no haya una máquina para resolverlo. El modelo es una especie de TM con oráculo, o un enfoque completamente diferente. Si sigues la tesis de la Iglesia, TM solo representa las máquinas que estamos usando hoy en día.
Eugene
16
Es la máquina más poderosa que sabemos construir . Bueno, en realidad no, solo podemos construir autómatas finitos.
Raphael
13
Su problema es que piensa en las TM como algo que vino después. No era. Fue (y es) usado para definir la clase de problemas computables de Turing . Se han encontrado muchos modelos equivalentes, pero eso no cambia la definición.
Raphael
3
Hay cientos de arquitecturas informáticas diferentes (Turing-complete), todas con conjuntos de instrucciones muy diferentes. No creo que sea obvio en absoluto que no hay ningún problema que uno pueda resolver pero otro no.
BlueRaja - Danny Pflughoeft
55
... ¿no es lo que estás diciendo simplemente la tesis de Church-Turing ? Hasta donde sabemos, nadie refutó la tesis, pero no podemos excluir la existencia de un modelo diferente de computación que sea "razonable" (es decir, de alguna manera implementable) y más fuerte que las TM.
Bakuriu

Respuestas:

135

Estoy de acuerdo en que una máquina de Turing puede resolver "todos los posibles problemas matemáticos".

Bueno, no deberías, porque no es cierto. Por ejemplo, las máquinas de Turing no pueden determinar si los polinomios con coeficientes enteros tienen soluciones enteras ( décimo problema de Hilbert ).

¿Es Turing Machine "por definición" la máquina más poderosa?

No. Podemos imaginar una jerarquía infinita de máquinas más poderosas . Sin embargo, la máquina de Turing es la máquina más poderosa que sabemos, al menos en principio, cómo construir. Sin embargo, esa no es una definición: es solo que no tenemos idea de cómo construir algo más poderoso, o si es posible.

¿Qué es lo nuevo que Alan Turing nos dio?

Una definición formal de algoritmo. Sin dicha definición (p. Ej., La máquina de Turing), solo tenemos definiciones informales de algoritmo, en la línea de "Un procedimiento finito para resolver algo". Vale genial. Pero, ¿qué pasos individuales pueden tomar estos procedimientos?

¿Son pasos básicos de operaciones aritméticas? ¿Encontrar el gradiente de una curva es un paso? ¿Encontrar raíces de polinomios es un paso? ¿Encontrar raíces enteras de polinomios es un paso? Cada uno de esos parece tan natural. Sin embargo, si los permite a todos, sus "procedimientos finitamente especificados" son más potentes que las máquinas de Turing, lo que significa que pueden resolver cosas que los algoritmos no pueden resolver. Si permite todo menos el último, todavía está dentro de los reinos del cálculo de Turing.

Si no tuviéramos una definición formal de algoritmo, ni siquiera podríamos hacer estas preguntas. No seríamos capaces de discutir lo que los algoritmos pueden hacer, porque no sabríamos lo que un algoritmo es .

David Richerby
fuente
3
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DW
¿No te refieres a soluciones racionales? Creo que las soluciones enteras son posibles en un número finito de pasos.
Trenin
2
@Trenin La página de Wikipedia que enlace dice "entero racional", que explica que es una frase que a veces se usa para distinguir los enteros ordinarios de objetos como los enteros gaussianos (números complejos donde ). a , b Za+iba,bZ
David Richerby
Entendido. Además, lo que pensé que era posible resulta ser mucho más difícil de lo que pensaba.
Trenin
64

No está en lo correcto cuando hace repetidamente las declaraciones sobre esto o aquello como "solo una tautología". Permítame poner sus afirmaciones en un contexto histórico.

En primer lugar, debe hacer que los conceptos que utiliza sean precisos. ¿Qué es un problema? ¿Qué es un algoritmo? ¿Qué es una máquina? Puede pensar que esto es obvio, pero una buena parte de las décadas de 1920 y 1930 fue gastada por lógicos tratando de resolver estas cosas. Hubo varias propuestas, una de las cuales fueron máquinas de Turing, que fue la más exitosa. Más tarde resultó que las otras propuestas eran equivalentes a las máquinas de Turing. Tienes que imaginar una era cuando la palabra "computadora" significa una persona, no una máquina. Simplemente estás montando la ola y las consecuencias de los inventos brillantes de mentes brillantes de hace cien años, sin darte cuenta.

Las máquinas de Turing se describen concretamente en términos de estados, un cabezal y una cinta de trabajo. Está lejos de ser obvio que esto agota las posibilidades informáticas del universo en el que vivimos. ¿No podríamos hacer una máquina más poderosa usando electricidad, agua o fenómenos cuánticos? ¿Qué pasa si volamos una máquina de Turing en un agujero negro a la velocidad y dirección correctas, para que pueda realizar infinitos pasos en lo que nos parece tiempo finito? No puede simplemente decir "obviamente no", primero debe hacer algunos cálculos en relatividad general. ¿Y qué pasa si los físicos descubren una forma de comunicarse y controlar universos paralelos, para que podamos ejecutar infinitas máquinas de Turing en tiempo paralelo?

No , no importa que en la actualidad no podemos hacer estas cosas. Sin embargo, lo importante es que comprenda que Turing tuvo que pensar en lo que era físicamente posible (basado en el conocimiento de la física en ese momento). No solo escribió "una mera tautología". Lejos de ello, analizó cuidadosamente lo que significa la computación en un sentido informal, luego propuso un modelo formal, argumentó con mucho cuidado que este modelo captura lo que la gente entendió por "computación", y derivó algunos teoremas importantes al respecto. Uno de estos teoremas dice que las máquinas de Turing no pueden resolver todos los problemas matemáticos (al contrario de una de sus declaraciones falsas). Todo esto, en un solo documento, escrito durante la vacunación de verano, mientras era estudiante.fue la invención de la idea de la computadora moderna de uso general. Después de eso, fue solo una simple cuestión de ingeniería.

¿Responde eso a lo que Turing contribuyó a la humanidad más allá de una mera tautología? ¿Y realmente leíste su periódico ?

Andrej Bauer
fuente
19
"Hay que imaginar una época en que la palabra" computadora "significa una persona, no una máquina". Este es un recordatorio realmente útil. En esencia, Turing intentó simular efectivamente, con su "máquina", las operaciones que una persona podía hacer con lápiz y papel en ese momento para calcular algo.
Sorrop
2
"Su teorema sobre la existencia de máquinas universales fue la invención de la computadora moderna de uso general". - Bueno ... en el mundo matemático, tal vez. Personas como Konrad Zuse desarrollaron computadoras de uso general de forma independiente.
Raphael
66
@AndrejBauer Eso todavía sugiere una línea de tiempo y dependencia que no estaba allí, no en todos los casos. No te culpo, pocas personas saben lo que hizo Zuse cuando. El hecho es que construyó computadoras desde 1935 a lo largo de la Segunda Guerra Mundial sin mucho o ningún aporte desde fuera de Alemania. También desarrolló su Plankalkül durante ese tiempo. Supongo que fue con las computadoras como con muchas otras cosas: el tiempo estaba maduro, muchas mentes pensaron en líneas similares. El punto es que, a pesar de todas sus contribuciones, Turing no inventó la informática .
Raphael
12
@Raphael: Konrad Zuse no sabía que su máquina puede procesar todos los problemas computables (ahora sabemos que sus máquinas ESTÁN completadas - memoria de módulo). Lo que contribuyó Turing NO fue la idea de que las máquinas puedan hacer cómputo; Babbage lo hizo antes de Zuse o Turing. A lo que contribuyó Turing fue a la idea de que los conjuntos de instrucciones y los lenguajes de programación realmente no importan en teoría. Esta no es una idea obvia. Irónicamente, es esta idea la que impulsa el desarrollo de CPU y lenguajes de programación
slebetman
1
"los conjuntos de instrucciones y los lenguajes de programación realmente no importan en teoría", eso es claramente falso. Las diferencias pueden importar, pero no siempre. Turing definió un cierto modelo de cómputo y afirmó que era tan poderoso como podría ser. Atrapado entre la advertencia de la memoria infinita y los modelos más poderosos, no estoy muy seguro de que esa afirmación sea válida. Entonces, en cierto modo, no hizo nada más que Zuse, si fuera con matemáticas en lugar de metal.
Raphael
23

Que "cualquier cosa que tenga solución puede ser representada por un algoritmo" no es obvio, en absoluto.

Este ha sido objeto de un intenso debate, ya que Alan Turing, reelaborando ideas de Alonzo Church, propuso una definición de números computables que tomó la forma de la máquina a la que se refiere. Es importante destacar que esas no eran las únicas personas que trabajaban en este tipo de cosas, en ese momento.

Todavía lo llamamos tesis, o conjetura, ya que "cualquier cosa que pueda calcularse" claramente no es un objeto matemático preciso, cuya estructura y rango podrían estudiarse de manera no especulativa.

André Souza Lemos
fuente
1
Pero cualquier cosa que tenga solución debe resolverse mediante un "proceso" (por definición). Es posible que no conozcamos el proceso para resolver un problema "solucionable" particular en el momento actual. En cuyo caso, significa que el problema es solucionable pero no puede resolverse ahora. ¿No significa efectivamente que "cualquier cosa que se pueda resolver puede ser representada por un algoritmo" porque "proceso" = "algoritmo". ¿Por qué dices que no es obvio?
Sounak Bhattacharya
13
¿Qué es un "proceso"? Mira, es fácil correr en círculos, sustituyendo un concepto poco claro por otro. El intento de Turing fue en realidad un experimento mental encarnado, que todavía alimenta nuestra imaginación, incluso hoy. Eso no es una cosa pequeña.
André Souza Lemos
@SounakBhattacharya Por algún proceso (de años y genio) Sir Andrew Wiles demostró que el Último Teorema de Fermat era cierto. ¿Te imaginas que hay una TM que podría haber tomado esa determinación?
OJFord
1
@OllieFord Bueno, si la prueba es lo suficientemente rigurosa como para que cada paso pueda expresarse en términos de axiomas bien especificados existentes, entonces la prueba puede ser verificada por una máquina de Turing. Entonces podríamos especificar una máquina de Turing que enumere todas las pruebas posibles y seguramente (pero muy muy lentamente) la máquina encontraría dicha prueba. Sin embargo, una implementación física simple de esa máquina Turing tomaría más de 400 años, y mucho más que la vida útil esperada del universo.
gmatht
19

Primero, es importante tener en cuenta que las Turing Machines fueron diseñadas inicialmente por Turing no como un modelo de cualquier tipo de computadora físicamente realizable, sino más bien como un límite ideal para lo que es calculable por un humano calculando en una mecánica paso a paso. manera (sin ningún uso de la intuición). Este punto es ampliamente incomprendido; vea [1] para una excelente exposición sobre este y otros temas relacionados.

Las limitaciones de finitud postuladas por Turing para sus Máquinas Turing se basan en las limitaciones postuladas del aparato sensorial humano. Las generalizaciones de los análisis de Turing a dispositivos informáticos físicamente realizables (y tesis análogas de Church-Turing) no llegaron hasta mucho más tarde (1980) debido a Robin Gandy, con limitaciones basadas en las leyes de la física. Como dice Odifreddi en la p. 51 de [2] (biblia de la teoría clásica de la recursión)

Las máquinas de Turing son dispositivos teóricos, pero se han diseñado teniendo en cuenta las limitaciones físicas. En particular, hemos incorporado en nuestro modelo restricciones que provienen de:

  • (a) ATOMISMO, asegurando que la cantidad de información que puede codificarse en cualquier configuración de la máquina (como un sistema finito) esté limitada; y

  • (b) RELATIVIDAD, al excluir acciones a distancia y hacer que el efecto causal se propague a través de interacciones locales. Gandy [1980] ha demostrado que la noción de máquina de Turing es lo suficientemente general como para incluir, en un sentido preciso, cualquier dispositivo informático que satisfaga limitaciones similares.

y en la p. 107: (Una teoría general de dispositivos discretos y deterministas)

El análisis (Church [1957], Kolmogorov y Uspenskii [1958], Gandy [1980]) parte de los supuestos del atomismo y la relatividad. El primero reduce la estructura de la materia a un conjunto finito de partículas básicas de dimensiones acotadas y, por lo tanto, justifica la posibilidad teórica de desmantelar una máquina a un conjunto de constituyentes básicos. Este último impone un límite superior (la velocidad de la luz) a la velocidad de propagación de los cambios causales, y por lo tanto justifica la posibilidad teórica de reducir el efecto causal producido en un instante t en una región limitada del espacio V, a las acciones producidas por las regiones. cuyos puntos están dentro de la distancia c * t desde algún punto V. Por supuesto, los supuestos no tienen en cuenta los sistemas que son continuos o que permiten la acción ilimitada de acción a distancia (como los sistemas gravitacionales newtonianos).

El análisis de Gandy muestra que EL COMPORTAMIENTO ES RECURSIVO, PARA CUALQUIER DISPOSITIVO CON UN LÍMITE FIJO SOBRE LA COMPLEJIDAD DE SUS POSIBLES CONFIGURACIONES (en el sentido de que tanto los niveles de acumulación conceptual a partir de los constituyentes, como el número de constituyentes en cualquier parte estructurada de cualquier configuración, están delimitados), Y FIJOS FINITOS, CONJUNTOS DE INSTRUCCIONES DETERMINISTAS PARA LA ACCIÓN LOCAL Y GLOBAL (el primero dice cómo determinar el efecto de una acción en partes estructuradas, el segundo cómo ensamblar los efectos locales). Además, el análisis es óptimo en el sentido de que, cuando se hace preciso, cualquier relajación de las condiciones se vuelve compatible con cualquier comportamiento, y por lo tanto proporciona una descripción suficiente y necesaria del comportamiento recursivo.

El análisis de Gandy ofrece una perspectiva muy esclarecedora sobre el poder y las limitaciones de las máquinas de Turing. Vale la pena leer para obtener más información sobre estos asuntos. Sin embargo, tenga en cuenta que el artículo de Gandy de 1980 [3] es considerado difícil incluso por algunos expertos. Puede resultarle útil examinar primero los documentos en [4] por J. Shepherdson y A. Makowsky.

[1] Sieg, Wilfried. Procedimientos mecánicos y experiencia matemática. [págs. 71--117 en Matemáticas y mente. Artículos de la Conferencia sobre Filosofía de las Matemáticas celebrada en Amherst College, Amherst, Massachusetts, del 5 al 7 de abril de 1991. Editado por Alexander George. Computación Lógica. Philos., Oxford Univ. Press, Nueva York, 1994. ISBN: 0-19-507929-9 MR 96m: 00006 (Revisor: Stewart Shapiro) 00A30 (01A60 03A05 03D20)

[2] Odifreddi, Piergiorgio. Teoría de la recursividad clásica. La teoría de funciones y conjuntos de números naturales. Con un prólogo de GE Sacks. Studies in Logic and the Foundations of Mathematics, 125. North-Holland Publishing Co., Amsterdam-Nueva York, 1989. xviii + 668 pp. ISBN: 0-444-87295-7 MR 90d: 03072 (Revisor: Rodney G. Downey ) 03Dxx (03-02 03E15 03E45 03F30 68Q05)

[3] Gandy, Robin. Tesis de la Iglesia y principios para los mecanismos. El simposio de Kleene. Actas del simposio celebrado en la Universidad de Wisconsin, Madison, Wisconsin, del 18 al 24 de junio de 1978. Editado por Jon Barwise, H. Jerome Keisler y Kenneth Kunen. Studies in Logic and the Foundations of Mathematics, 101. North-Holland Publishing Co., Amsterdam-Nueva York, 1980. xx + 425 pp. ISBN: 0-444-85345-6 MR 82h: 03036 (Revisor: Douglas Cenzer) 03D10 (03A05)

[4] La máquina universal de Turing: una encuesta de medio siglo. Segunda edicion. Editado por Rolf Herken. Computerkultur [Cultura informática], II. Springer-Verlag, Viena, 1995. xvi + 611 pp. ISBN: 3-211-82637-8 MR 96j: 03005 03-06 (01A60 03D10 03D15 68-06)

Bill Dubuque
fuente
2
¡Muchas gracias! Siempre sentí que las máquinas de Turing eran extrañamente poco elegantes, pero esto explica de manera justa por qué eso puede ser mal interpretado.
PJTraill
6

La mejor discusión popular sobre esta pregunta que he leído es el ensayo del profesor Scott Aaronson del MIT ¿Quién puede nombrar el número más grande? , en el que explora, entre otras cosas, las implicaciones de las máquinas super-Turing, las máquinas super-duper-Turing y las máquinas super-duper-pooper-Turing.

James Brock
fuente
2
Después de "super-duper-pooper" viene "super-duper-ooper-flooper", o al menos eso es lo que parece recordar de cuando tenía unos 7 u 8 años. Probablemente sea la terminología formal correcta.
Peter Cordes
4

No, los TM no son los más poderosos. Dos ejemplos:

a) Podría haber otras máquinas que calculen los mismos resultados que una TM pero algorítmicamente más rápido (por ejemplo, computadoras cuánticas que calculan factores primos). "Más rápido" es un tipo de poder.

b) Los TM no pueden representar números reales generales con precisión perfecta. Pero una computadora analógica (CA) podría representar y hacer aritmética con números reales con precisión perfecta. Esto sería más poderoso que cualquier TM.


Por supuesto (b) requiere que nuestro universo tenga algunas propiedades continuas (¿gravedad?) Que la CA puede usar para representar valores reales. Quizás todas las propiedades físicas, incluida la gravedad, están cuantizadas. Pero podemos especular sobre máquinas en un universo continuo. Por lo tanto, los TM no son más poderosos "por definición".

Adam Gawne-Cain
fuente
3
Bienvenido al sitio! "Más poderoso" en el contexto de la teoría de la computación generalmente se entiende como "capaz de calcular más funciones", en lugar de "capaz de calcular en menos pasos", por lo que no estoy seguro de que su (a) realmente cuente. Además, no está claro cómo una computadora podría usar valores reales. ¿Cómo ingresaría un valor real que no fuera, digamos, un real computable? ¿Cómo le dirías a alguien más qué valor deberían ingresar a su máquina continua y cómo lidiarías con el ruido? Pero tal vez sea una objeción tonta como "Cómo producirías suficiente cinta para que la máquina Turing la use".
David Richerby
-4

Si observa la complejidad computacional, una máquina de Turing es la máquina más poderosa, porque tiene memoria ilimitada y ninguna máquina real tiene eso. Cualquier máquina real no puede resolver problemas de tamaño arbitrario; ni siquiera pueden leer un problema, mucho menos resolverlo.

Por otro lado, si trató de implementar una máquina de Turing real, supongamos que se detiene y suena una alarma si se queda sin cinta, encontrará que tomaría muchos más pasos para hacer cualquier tipo de cálculo que digamos la máquina real en un teléfono barato, y sería mucho más lento para resolver problemas reales. También encontrará que escribir una respuesta en una cinta no es una muy buena interfaz de usuario. Y descubrirá que muchas personas usan computadoras no para resolver problemas, sino para enviar fotos de desnudos a sus amigos y para mirar videos de gatos, y una Máquina de Turing no sirve para nada.

gnasher729
fuente
12
¿Podría aclarar cómo responde esto a la pregunta?
David Richerby
1
Obviamente, una máquina de Turing real podría procesar fotos y videos. Por supuesto, se necesitaría algún tipo de dispositivo de salida de imagen para que los humanos los vean, pero eso se aplica a cualquier computadora; una CPU + memoria en una placa de circuito tampoco es "ningún uso para eso".
hyde
1
¡Entre los modelos de máquina con memoria infinita, los TM no son los más potentes!
Raphael