¿Por qué la integridad de Turing es correcta?

15

Estoy usando una computadora digital para escribir este mensaje. Tal máquina tiene una propiedad que, si lo piensa, es realmente notable: es una máquina que, si se programa adecuadamente, puede realizar cualquier cálculo posible .

Por supuesto, las máquinas de calcular de un tipo u otro vuelven a la antigüedad. La gente ha construido máquinas para realizar sumas y restas (p. Ej., Un ábaco), multiplicación y división (p. Ej., La regla de cálculo) y más máquinas específicas del dominio, como calculadoras para las posiciones de los planetas.

Lo sorprendente de una computadora es que puede realizar cualquier cálculo. Cualquier cálculo en absoluto. Y todo sin tener que volver a cablear la máquina. Hoy todos dan por sentada esta idea, pero si te detienes y piensas en ello, es sorprendente que tal dispositivo sea posible.

Tengo dos preguntas reales :

  1. ¿Cuándo descubrió la humanidad que tal máquina era posible? ¿Ha habido alguna duda seria sobre si se puede hacer? ¿Cuándo se resolvió esto? (En particular, ¿se resolvió antes o después de la primera implementación real?)

  2. ¿Cómo probaron los matemáticos que una máquina completa de Turing realmente puede calcular todo?

Ese segundo es complicado. Todo formalismo parece tener algunas cosas que no se pueden calcular. Actualmente, la "función computable" se define como "cualquier cosa que una máquina de Turing pueda calcular". Pero, ¿cómo sabemos que no hay una máquina un poco más poderosa que pueda calcular más cosas? ¿Cómo sabemos que las máquinas de Turing son la abstracción correcta?

Orquídea matemática
fuente
77
Las computadoras (y sus modelos teóricos, como las máquinas de Turing) NO PUEDEN calcular todo. Echa un vistazo, por ejemplo, al problema de detención .
2
Respuesta a la segunda pregunta: no probamos esto; es una cuestión de definición; Resulta que lo que pensamos intuitivamente de "computable" es computable por las máquinas de Turing (o cualquier cosa equivalente). Esta afirmación se conoce como tesis de Church-Turing .
sdcvvc
2
Las máquinas como su PC que tienen memoria finita no son equivalentes a Turing. Las máquinas de Turing tienen una cinta ilimitada, lo que significa que cuanto más tiempo continúa un cálculo, más memoria pueden potencialmente usar. Las PC no pueden realizar cálculos que requieren un tiempo limitado pero que requieren más almacenamiento del que tienen disponible.
Mike Samuel
3
@ MikeSamuel esta es una distinción pedante y similar a decir "hay un número finito de partículas en el universo, por lo tanto, todo es un estado finito". Es una declaración verdadera, pero no útil. Rara vez es útil modelar una computadora del mundo real como una máquina de estados finitos.
Artem Kaznatcheev

Respuestas:

17

La humanidad formalizó el cómputo y desarrolló dos sistemas para él en 1936 con los documentos seminales de la Iglesia Alonzo sobre cálculo λ y Alan Turing (que hoy, 23 de junio de 2012, cumpliría 100 años si no fuera por circunstancias despreciables que conducen a su fallecimiento temprano) lo que se conoció como máquinas de Turing. Ambos matemáticos estaban resolviendo el problema de Entscheidung .

Aunque el artículo de Church se publicó un poco antes, Turing no lo sabía cuando desarrolló sus ideas, y el enfoque de Turing resultó ser más útil para el diseño de máquinas del mundo real. Esto se debió a que mostró cómo diseñar una máquina universal de Turing que se pudiera programar para ejecutar cualquier cálculo. Esta máquina universal, con una arquitectura concreta basada en el trabajo de John von Neumann, es la idea básica detrás de la máquina en la que está leyendo mi respuesta.

Como notó, computable se define como "computable en una máquina de Turing" y todos los demás modelos razonables de cómputo han demostrado ser equivalentes en su poder. La creencia de que todos los modelos razonables de cómputo son equivalentes en los problemas de decisión que pueden resolver se conoce como la tesis de Church-Turing . En su forma original, la comunidad erudita lo cree casi por completo. De hecho, no está completamente claro lo que significaría probar / refutar la tesis de la Iglesia-Turing ; en muchos sentidos se convierte en una pregunta empírica.

λ computable) la computación cuántica sigue siendo equivalente al modelo de Turing.

Artem Kaznatcheev
fuente
1
El artículo de Turing de 1936, en comparación con el trabajo de Church en ese momento, era mucho más convincente en su argumento de que cualquier función numérica que un humano pueda calcular algorítmicamente puede ser calculada por una máquina de Turing. Los formalismos de Church obviamente no tenían esa propiedad, y hasta el día de hoy la reducción de otros sistemas computacionales a las máquinas de Turing es vital debido al análisis original de Turing de lo que las máquinas de Turing pueden calcular.
Carl Mummert
1
@CarlMummert Definitivamente estoy de acuerdo, pero el trabajo de Church debe mencionarse por completo. Además, no es para nada insignificante, mientras que la mayor parte de la Teoría A se basa en TM, la Teoría B es mucho más amigable con lambda-calc. Por lo tanto, también es parcialmente una diferencia de culturas.
Artem Kaznatcheev
Espera, ¿entonces estás diciendo que no se ha demostrado que no haya un sistema computacional más poderoso? ¿Es simplemente una suposición ?
MathematicalOrchid
@MathematicalOrchid todos los modelos razonables de cómputo (razonable significa más o menos: al mismo tiempo trabajar solo en secciones finitas de objetos y solo hacer una de las muchas opciones finitas) con las que estoy familiarizado se han demostrado equivalentes a las máquinas de Turing.
Artem Kaznatcheev
2
@MathematicalOrchid Para proporcionar una respuesta potencialmente más directa a su pregunta de seguimiento: correcto, nadie ha demostrado que no exista un modelo razonable de computación más poderoso que una TM. "Asunción" es una palabra para ello; La "hipótesis" es otra. Podríamos despertarnos mañana y ver un nuevo y mejor modelo de computación en CNN. Es poco probable, pero posible.
Patrick87
-2

Hay una razón por la que se llama Máquina de Turing, y es porque fue inventada por Alan Turing. Hizo un artículo de 1936 sobre él, estableciendo estos conceptos. Si desea saber más sobre las máquinas de Turing, consulte el documento. Se dudó seriamente, antes de diseñar y construir uno que descubriera el Enigma, que este concepto realmente podría funcionar. Sin embargo, los británicos estaban bastante desesperados y él era un genio, por lo que confiaron en él y valió la pena enormemente.

Sin embargo, cuando lo piensas un poco más, realmente no es tan sorprendente en absoluto. Se sabía mucho antes de Turing que todas las matemáticas podrían reducirse a un conjunto de axiomas. Todo lo que tendría que hacer es dar al conjunto de instrucciones la capacidad de realizar estos axiomas, y listo.

Perrito
fuente
Turing no diseñó ni construyó enigma (aunque sí diseñó otra computadora que nunca se construyó). Su segundo párrafo está bien hecho: mucha de la emoción en torno al tiempo de Turing (y de hecho este fue el punto de su propio artículo) relacionada con los límites de la computación.
Marcin
¿Confiamos en él? Solo hasta que se demostró públicamente que era homosexual, lo matamos por eso. También se ha demostrado que hay un conjunto de problemas que se pueden establecer dentro de cualquier marco axiomático que nunca se puede probar con esos axiomas.
@ TonyHopkinson: Lo sé. Sin embargo, el trabajo de la TM no es calcular todo , sino solo calcular lo que se puede calcular. Su declaración solo dice que hay algunos cálculos que no pueden probarse que sean correctos. Eso no significa que no se puedan hacer.
@Marcin: Nunca, implicaba que Turing diseñó o construyó el Enigma. Dije que jugó un papel crítico en la máquina que descifró el Enigma.
77
Esta respuesta es incorrecta . Turing no diseñó una TM para descifrar el enigma, ayudó a diseñar el Bombe, que era una máquina especializada para atacar el cifrado Enigma y no universal. Además, no se sabía que las matemáticas podrían reducirse a un conjunto de axiomas. De hecho, en 1931, Godel demostró lo contrario y es sobre las ideas de esta prueba que se basó el trabajo de Turing. Incluso el comentario inicial sobre la lectura del artículo original de Turing es engañoso. Aunque el documento es excelente, si solo quieres aprender lo básico, un libro de texto moderno como Sipser es mejor.
Artem Kaznatcheev