Dsfdñlkf

MÁQUINA DE TURING
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. Losprimeros 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ónabstracta 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 unode 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 cuadradoadyacente, 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 tablade 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 elpapel 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 decomputadora (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...