La maqina de turing

Maquina de Turing

Historia de la máquina de Turing:

Alan Mathison Turing (1912–1954) fue un hombre extremadamente talentoso, que tuvo influencia en el desarrollo de la informática y proporcionó una formalización del concepto del algoritmo y la computación con su famosa máquina Turing , desempeñando un papel importante en la creación de Computadora moderna. Turing descubrió algo que habría deleitado a Leibniz: descubrió que, en principio, era posible idear una única máquina universal que, por sí sola, pudiera realizar cualquier cálculo posible.

Turing describió por primera vez la máquina Turing en su artículo de 1936 sobre números computables, con una aplicación al problema Entscheidungs .

La máquina Turing es un dispositivo informático idealizado, que consiste en un cabezal de lectura / escritura (o escáner ) con una cinta de papel que lo atraviesa. La cinta se divide en cuadrados, cada cuadrado con un solo símbolo ( 0 o 1 , por ejemplo). Esta cinta es el medio de almacenamiento de propósito general de la máquina, que sirve tanto como vehículo para la entrada y salida como una memoria de trabajo para almacenar los resultados de los pasos intermedios de la computación. En el artículo original de 1936, Turing en realidad no imagina una máquina mecánica, sino una persona a la que llama la computadora , que ejecuta estas reglas mecánicas deterministas de una manera descuidada .

La entrada que está inscrita en la cinta antes de que comience el cálculo debe consistir en un número finito de símbolos. Sin embargo, la cinta tiene una longitud ilimitada, ya que el objetivo de Turing era mostrar que hay tareas que estas máquinas no pueden realizar, incluso con memoria de trabajo ilimitada y tiempo ilimitado. El cabezal de lectura / escritura es programable. Para calcular con el dispositivo, debe programarlo, inscribir la entrada en la cinta, colocar la cabeza sobre el cuadrado que contiene el símbolo de entrada más a la izquierda y poner la máquina en movimiento. Una vez que se completa el cálculo, la máquina se detendrá con la cabeza colocada sobre el cuadrado que contiene el símbolo más a la izquierda de la salida (o en otro lugar si está programado).

La máquina Turing puede realizar seis tipos de operaciones fundamentales: leer, escribir, moverse hacia la izquierda, moverse hacia la derecha, cambiar de estado y detenerse. Un cálculo complicado puede consistir en cientos de miles, o incluso millones de tales operaciones. A pesar de la simplicidad de la máquina Turing, es capaz de calcular cualquier cosa que cualquier computadora moderna pueda calcular.

Turing dio una breve definición del experimento mental en su ensayo de 1948, Intelligent Machinery . Refiriéndose a su publicación de 1936, escribe que la máquina de Turing, llamada aquí Máquina de computación lógica , consistía en:
... una capacidad de memoria infinita obtenida en forma de una cinta infinita marcada en cuadrados en cada uno de los cuales se podría imprimir un símbolo. En cualquier momento hay un símbolo en la máquina; Se llama el símbolo escaneado. La máquina puede alterar el símbolo escaneado y su comportamiento está determinado en parte por ese símbolo, pero los símbolos en la cinta en otro lugar no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esta una de las operaciones elementales de la máquina. Por lo tanto, cualquier símbolo en la cinta puede eventualmente tener entradas.

En Intelligent Machinery, Turing también afirmó que una máquina de pensar debería tener la mente en blanco de un bebé en lugar de una mente adulta llena de opiniones e ideas. El ensayo contenía una discusión temprana de redes neuronales. calculó que tomaría una batería de programadores 50 años llevar esta máquina de aprendizaje desde la madurez mental de la infancia hasta la de adultos.

En 1950, Turing publicó un documento seminal sobre el tema de la inteligencia artificial: Maquinaria de computación e inteligencia , en el que describió la "Prueba de Turing" para determinar si una máquina es "inteligente".

La mayor contribución de Turing al desarrollo de la computadora digital es:
   1. La idea de controlar la función de una máquina informática almacenando un programa de instrucciones codificadas simbólica o numéricamente en la memoria de la máquina.
   2. Su prueba de que, por este medio, una sola máquina (una máquina universal) es capaz de realizar todos los cálculos que cualquier otra máquina de Turing puede llevar a cabo. Afirmó: Las computadoras electrónicas están destinadas a llevar a cabo cualquier proceso de regla general que podría haber sido realizado por un operador humano que trabaja de manera disciplinada pero no inteligente .

Turing era homosexual, y esto resultó en un enjuiciamiento penal en 1952 (los actos homosexuales eran ilegales en el Reino Unido en ese momento), y aceptó el tratamiento con hormonas femeninas (castración química), como alternativa a la prisión. Murió en 1954, varias semanas antes de cumplir 42 años, de un envenenamiento por cianuro aparentemente autoadministrado. El 10 de septiembre de 2009, luego de una campaña en Internet, el primer ministro británico, Gordon Brown, hizo una disculpa pública oficial en nombre del gobierno británico por la forma en que Turing fue tratado después de la guerra.

Características de la máquina de Turing:

La máquina de Turing modela matemáticamente una máquina que opera mecánicamente en una cinta. En esta cinta hay símbolos, que la máquina puede leer y escribir, uno a la vez, usando un cabezal de cinta. La operación está totalmente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escriba un 1; si el símbolo visto es 1, cambie al estado 17; en el estado 17, si el símbolo visto es 0, escribe un 1 y cambia al estado 6; " etc. En el artículo original (" Sobre números computables, con una aplicación al problema Entscheidungs ", ver también las referencias a continuación ), Turing no imagina un mecanismo, sino una persona a la que llama la "computadora", que ejecuta servilmente estas reglas mecánicas deterministas. (o como dice Turing, "de una manera desganada").

La cabeza siempre está sobre un cuadrado particular de la cinta; solo se muestra un tramo finito de cuadrados. La instrucción a realizar (q 4 ) se muestra sobre el cuadrado escaneado. (Dibujo según Kleene (1952) p. 375.)

Aquí, el estado interno (q 1 ) se muestra dentro de la cabeza, y la ilustración describe la cinta como infinita y precargada con "0", el símbolo en blanco. El estado completo del sistema (su "configuración completa") consiste en el estado interno, cualquier símbolo que no esté en blanco en la cinta (en esta ilustración "11B") y la posición del cabezal con respecto a esos símbolos, incluidos los espacios en blanco, es decir, "011B ". (Dibujo según Minsky (1967) p. 121.)

...