El siguiente artículo es un complemento del artículo Máquina de Turing .
Máquina de Turing como dispositivo mecánico
La máquina de Turing que se muestra aquí consiste en una cinta de papel especial que se puede borrar y escribir con una "marca de conteo". Quizás la TABLE esté hecha de un lector de cinta de papel de "sólo lectura" similar, o quizás lea tarjetas perforadas . El biógrafo de Turing, Andrew Hodges (1983), ha escrito que a Turing de niño le gustaban las máquinas de escribir . GH Hardy , uno de los maestros de Turing, había sugerido una "'máquina milagrosa', un proceso mecánico que podría funcionar en el problema de decisión de Hilbert " (Hodges, pág. 98) . Sin embargo, "su máquina no tenía un modelo evidente en nada de lo que existía en 1936, excepto en términos generales de las nuevas industrias eléctricas, con sus teleimpresoras , ' escaneo ' de televisión y conexiones automáticas de central telefónica . Fue un invento suyo". (Hodges pág.109)
Davis (2000) dice que Turing construyó un multiplicador binario a partir de relés electromecánicos (p. 170). Como se señaló en la sección de historia del algoritmo , la cinta de papel perforada o impresa y las tarjetas de papel perforadas eran algo común en la década de 1930.
Boolos y Jeffrey (1974, 1999) señalan que "estar en un estado u otro podría ser una cuestión de tener uno u otro engranaje de cierta marcha hacia arriba ..." (p. 21).
La máquina de Turing como una "taza pobre" dentro de una caja tirando de la caja a lo largo de un riel
- "No nos preocupa la mecánica o la electrónica del asunto. Quizás la forma más sencilla de imaginar la cosa es bastante cruda: dentro de la caja hay un hombre, que hace toda la lectura y escritura y borra y mueve. (La caja no tiene fondo: la pobre taza simplemente camina entre las ataduras, tirando de la caja con él.) El hombre tiene una lista de m instrucciones escritas en una hoja de papel. Él está en estado qi cuando está llevando a cabo la instrucción número i [etc.] "(Boolos y Jeffrey (1974, 1999) p.21)
Esta descripción sigue de cerca la "Formulación I" de Emil Post para un "proceso combinatorio finito": un hombre, equipado y siguiendo un "conjunto fijo e inalterable de instrucciones", moviéndose hacia la izquierda o hacia la derecha a través de "una secuencia infinita de espacios o cajas". y mientras está en una caja, ya sea imprimiendo en una hoja de papel un solo "trazo vertical" o borrándolo (Post 1936 reimpreso en Indecidible p. 289). La formulación de Post fue la primera de este tipo que se publicó; precedió al de Turing en unos pocos meses.
Ambas descripciones, Post y Boolos y Jeffrey, utilizan 4 tuplas más simples en lugar de 5 tuplas para definir las 'configuraciones m' (instrucciones) de sus procesos.
Un robot lleva a cabo las instrucciones.
Este modelo fue sugerido por Stone (1972):
- "Adoptemos el punto de vista de que una computadora es un robot que realizará cualquier tarea que pueda describirse como una secuencia de instrucciones" (p. 3).
Stone usa el robot para desarrollar su noción de algoritmo . Esto a su vez lo lleva a su descripción de la máquina de Turing y su declaración:
- "La evidencia parece indicar que cada algoritmo para cualquier dispositivo informático tiene un algoritmo de máquina de Turing equivalente ... si [la tesis de Church] es cierta, es ciertamente notable que las máquinas de Turing, con sus operaciones extremadamente primitivas, sean capaces de realizar cualquier cálculo que cualquier otro dispositivo puede realizar, sin importar cuán complejo sea el dispositivo que elijamos ". (pág.13)
Referencias
Consulte el artículo principal de la máquina de Turing para obtener referencias.