Maquina de Turing

MAQUINA DE TURING:
una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentrode un computador.
La máquina de Turing fue descrita por Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society, La máquina de Turing no estádiseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender loslímites del cálculo mecánico.
Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina deTuring, aquí llamada una máquina de computación lógica, consistía en:
una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podríaimprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por esesímbolo, pero los símbolos en otros lugares de la cinta 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 esto unade las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad.

Una máquina de Turing que es capaz de simular cualquier otramáquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentadapor Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una formal teoría de la computación conocida como la tesis de Church-Turing. La tesis señala que las...