Somos el museo virtual más grande y mejor en español.

contadores web

Las máquinas de Turing fueron propuestas por primera vez por Alan Turing, en un intento para dar una definición matemática precisa de algoritmo o procedimiento mecánico. Los primeros trabajos de Turing y Alonzo Church abrieron la rama de la lógica matemática, que eventualmente se convertiría en la Teoría de Funciones Recursivas.

Una máquina de Turing es una representación abstracta de un dispositivo de cómputo o informático. Consiste en una cabeza de lectura/escritura que examina una dimensión posiblemente infinita de una cinta bidireccional dividida en cuadros cada uno de los cuales está identificado con un 0 o un 1. El Cómputo empieza con la máquina, en un estado dado, examinando un cuadrado. Borra lo que encuentra allí, imprime un 0 o 1, se mueve a un cuadrado adyacente, y entra en un nuevo estado. Esta conducta es completamente determinada por tres parámetros: (1) el estado en que la máquina está, (2) el número en el cuadrado está examinando, y (3) una tabla de instrucciones. La tabla de instrucciones especifica, para cada estado y entrada binaria, lo que la máquina debe escribir, en qué dirección se debe mover, y en qué estado debe entrar. (Por ejemplo, "Si en Estado 1 examina un 0: imprima 1, se mueve a la izquierda, y entra en Estado 3".) La tabla puede enlistar únicamente estados finitos, cada uno de los cuales se define implícitamente por el papel que juega en la tabla de instrucciones. Estos estados están a menudo referidos como "estados funcionales" de la máquina.
Por consiguiente, una máquina de Turing es más como un programa de computadora (software) que una computadora en sí (hardware). Cualquier máquina de Turing dada puede comprenderse o implementarse en un número infinito de dispositivos físicos de cómputo diferentes. Científicos de la computación y logistas han mostrado que si las computadoras digitales convencionales son consideradas en aislamiento de las entradas externas aleatorias (como un flujo de bits generado por decaimiento radiactivo), entonces dado bastante tiempo y cinta, las máquinas de Turing pueden computar cualquier función que cualquier computadora digital convencional puede computar. (Nosotros no consideraremos si las máquinas de Turing y las computadoras digitales modernas pueden ser equivalentes cuando a las dos se les dan las entradas externas, dado que eso exigiría cambiar la definición de la máquina de Turing.) También, un ‘atómata probabilístico' puede definirse como una máquina de Turing en la que la transición de la entrada y estado a la salida y estado toma lugar como una cierta probabilidad (Por ejemplo "Si en Estado 1 se examina un 0: (a) hay un 60% probabilidad que la máquina imprimirá 1, se moverá a la izquierda, y entra en Estado 3, y (b) hay un 40% de probabilidad que la máquina imprimirá 0, se moverá a la izquierda, y entrará en Estado 2".)

[634] [635]

Ligas de interés

Tu cumpleaños en la historia de la computación Trivia ¿Sabías tu que...? Buzón de comentarios

Un miembro de

The History Of Computing  Foundation

Aceptamos saludos, felicitaciones, colaboraciones, aportaciones, información, sugerencias, patrocinios, donaciones en capital o especie.
Museo de la Informática y Computación Aplicada, DR(C) Héctor Francisco Rentería Toledo, 2003 - 2015 en trámite