[Las máquinas de estado finito, también llamadas autómatas finitos,] operan en pasos claramente separados o discretos que van de una a otra de un número de configuraciones (o estados). Estas máquinas, sumamente idealizadas, interesan por una cantidad de razones. ( Minsky 67, p. 11)
Una característica sobresaliente de las máquinas de estado finito es la relación simple entre su estructura y su comportamiento. Una vez que tenemos (1) la descripción de un autómata, (2) su condición o estado inicial, y (3) una descripción de las señales que le llegarán de su entorno, podemos calcular cuál será su estado en cada momento sucesivo.
................
La teoría de las máquinas de estado finito lidia con el tiempo de una manera muy peculiar. El comportamiento de una máquina se describe como una secuencia lineal simple de eventos en el tiempo. Estos eventos ocurren solamente en momentos discretos: la variable de tiempo t toma únicamente los valores 0, 1, 2,... ( Minsky 67, p. 12)
Desde el punto de vista del usuario (o del entorno), una máquina puede normalmente mirarse como una caja cerrada con canales de entrada y de salida. De vez en cuando el usuario actúa sobre la máquina por los canales de entrada y de vez en cuando la máquina actúa sobre el usuario por los canales de salida.... Cuando lidiamos con una máquina de este modo, nos referimos a ella como una "caja negra", indicando nuestra despreocupación por sus interioridades. Trataremos los canales de entrada y salida con igual despreocupación.
................
Lo que nos preocupa es el conjunto de estados distinguibles que puede caracterizar un canal en determinado momento. En cada uno de nuestros momentos discretos de tiempo, cada canal se encontrará en uno u otro de un número finito de estados o condiciones posibles.
................
La presuposición de que el número de estados posibles de un canal es finito es uno de los postulados clave de la teoría de autómatas. ( Minsky 67, p. 13)
El estado de salida en el momento t no depende del estado de entrada en el mismo momento t. Esto es lo mismo que decir que no admitiremos la posibilidad de que las señales atraviesen la unidad de manera instantánea. Pero la salida del tiempo t + 1 normalmente dependerá, al menos en parte, de la señal de entrada en el momento previo t. ( Minsky 67, p. 14)
Las dos funciones de los autómatas finitos son las siguientes NOTA 2:
F: R(t+1) = F(E(t),I(t))
es decir, la salida en el tiempo t + 1 depende solo del insumo en el momento t y del estado en el tiempo t.
G: E(t+1) = G(E(t),I(t))
es decir, el estado E(t+1) depende solo del insumo previo I(t) y del estado previo E(t). ( Minsky 67, p. 16-17)
Una máquina de estado finito queda completamente descrita cuando nos dan sus funciones de "transición" F y G. ( Minsky 67, p. 20)
Una máquina de estado finito, dejada completamente a su libre
juego, caerá eventualmente en un patrón periódico
perfectamente repetitivo. La duración de este patrón repetitivo
no puede exceder el número de estados internos de la máquina,
y puede ser bastante menor. (
Minsky
67, p. 24)
Una máquina Turing es un mecanismo computacional hipotético formado por una unidad de control de estado finito acoplada a una cinta infinita. Cada paso en una computación de máquina Turing consiste en escribir un símbolo en la cinta, correr la cinta hacia la izquierda o hacia la derecha y adquirir un nuevo estado interno. La acción particular que se realiza en cada paso está determinada por el estado actual de la máquina y el símbolo rastreado en ese momento. A causa de la naturaleza simple y mecánica de sus computaciones, las máquinas Turing pueden ciertamente ser consideradas como algoritmos eficaces. La clara percepción de las capacidades de las máquinas Turing pueden, entonces, verter alguna luz sobre la naturaleza de las funciones eficazmente calculables.
Aunque las movidas atómicas disponibles en una máquina Turing son muy elementales, apropiadas secuencias de ellas pueden ser usadas para llevar a cabo una amplia variedad de operaciones de manipulación de patrones. Estas operaciones incluyen formar copias de bloques o patrones especificados, sustituir un bloque o patrón por otro, compararlos entre sí. Usando estas operaciones básicas como subrutinas, es posible diseñar máquinas Turing que realizan computaciones muy elaboradas.
Hay varias maneras en que el modelo básico de la máquina Turing puede ser modificado sin que se afecten sus capacidades últimas de computación. Entre las generalizaciones del modelo que no aumentan su poder computacional están el uso de cintas con varias pistas, el uso de más de una cabeza lectora o el uso de más de una cinta. Entre las restricciones que no disminuyen el poder del modelo básico están el uso de cintas infinitas en sólo una dirección, la limitación a un solo símbolo no blanco o la limitación a solo dos estados internos. Así, aunque una variante del modelo de máquina Turing puede resultar más eficiente o conveniente que otra para una aplicación dada, las capacidades fundamentales de las máquina Turing no dependen de la variante particular adoptada. ( Hennie 77, pp. 23-24)
Una máquina Turing consiste en una cinta indefinidamente larga acoplada a una unidad de control finita.... La cinta, que actúa como la memoria de la máquina, está dividida en cuadrados. Cada cuadrado puede ser estampado con un solo símbolo del alfabeto finito designado o puede estar en blanco.... La unidad de control puede correr la cinta para los dos lados al través de la cabeza lectora, pero en un momento particular la cabeza lectora puede examinar, o rastrear, solamente un cuadrado de la cinta.
La unidad de control es capaz de asumir cualquiera de un número fijo y finito de configuraciones o estados.... El estado de la unidad de control en un determinado momento, junto con el símbolo rastreado por la cabeza lectora, determina unívocamente cómo se comportará la máquina en ese momento. Las acciones disponibles para una máquina Turing son muy limitadas; puede ser o bien parar, y de este modo terminar su operación, o realizar una movida particular. Cada movida consiste en escribir un símbolo en el cuadrado de cinta rastreado ahora, correr la cinta un cuadrado a la izquierda o a la derecha, y provocar la entrada de la unidad de control en un nuevo estado. Por supuesto, el símbolo que la máquina escribe en su cinta puede no diferir del que está ya ahí, y el nuevo estado puede no diferir del actual.
La operación de una máquina Turing se caracteriza por la siguiente secuencia de eventos. La máquina recibe inicialmente una cinta en la cual algún número finito de cuadrados están estampados con símbolos y el resto permanece en blanco. Un determinado cuadrado de la cinta es designado para estar inicialmente bajo la cabeza lectora, y la unidad de control es forzada a asumir un cierto estado inicial predesignado. La máquina pasa entonces por una computación que consiste en una serie de movidas básicas. Esta computación puede continuar indefinidamente, o puede terminar después de un número finito de movidas. Si de hecho termina, el patrón de símbolos que queda en la cinta se toma como el resultado de la computación.
La acción que una máquina Turing toma en un determinado paso de una computación depende de la combinación específica de estado interno y símbolo rastreado que experimenta a cada paso, y en la manera en que la máquina particular haya sido diseñada....
................
Una máquina Turing puede ser interpretada como un algoritmo que convierte una hilera de símbolos en otra. La hilera inicial se hace estampar en la cinta de la máquina, y la hilera es colocada apropiadamente bajo la cabeza lectora. La máquina es entonces lanzada a la realización de su computación, según lo dicte su estructura interna fija. Si la computación termina, el producto del algoritmo es el patrón de cinta resultante; si la computación no termina, el resultado del algoritmo queda indefinido. ( Hennie 77, pp. 57-60)
El modelo de máquina Turing es importante porque se cree que el conjunto de los cálculos que pueden ejecutar las máquinas Turing incluye todos los cálculos que cualquier máquina puede realizar. Este aserto no puede ser probado, porque la frase "cualquier máquina" incluye máquinas todavía no inventadas. Sin embargo, puede mostrarse que las máquinas Turing computan todas las funciones recursivas parciales; los matemáticos creen que esta clase incluye todas las funciones que pueden computarse....
................
El modelo de máquina Turing tiene una máquina de estado finito conectada a una cabeza lectora y escritora que se mueve sobre una cinta infinita. La cinta infinita está dividida en "cuadrados", cada uno de los cuales contiene un símbolo escogido de un cierto conjunto T={T1, ...,Tn}, donde T1 (a menudo referido como b) denota el símbolo blanco. En cualquier momento, todos menos un número finito de cuadros estarán en blanco (contendrán b). La cabeza lectora/escritora puede examinar y cambiar el contenido de un solo cuadrado cada vez. La acción de la máquina durante una movida está determinada por el símbolo bajo la cabeza lectora/escritora y el estado interno (miembro de un conjunto finito S={S1,...,Sm}). La acción puede incluir un cambio del estado de la máquina, del símbolo debajo de la cabeza lectora/escritora, y de la posición de esta sobre la cinta. En el modelo de Turing todos estos cambios pueden hacerse en cada movida....
................
La máquina tiene una cinta que es infinita en ambas direcciones, con una cabeza lectora/escritora que examina un cuadrado en cada momento. En un paso la máquina examina el símbolo bajo la cabeza lectora/escritora y el estado actual para determinar:
2. Un movimiento de la cabeza lectora a lo largo de la cinta; la cabeza se mueve un cuadrado a la izquierda ( L) o un cuadrado a la derecha ( R).
3. El estado siguiente de la máquina de estado finito.
4. Si parar o no.
Como cualquier máquina Turing tiene un número finito de estados y un alfabeto de cinta finito, puede ser descrita por una tabla de transiciones, grafo de transiciones o diagrama de flujo. Cada transición debe especificar el nuevo símbolo en el cuadrado bajo la cabeza lectora/escritora, la dirección del movimiento de la cabeza, y el nuevo estado....
La información en la tabla de transiciones puede ser enumerada mediante el enlistado de cada movida posible como un quíntuplo. Los primeros dos elementos del quíntuplo son el estado presente y el símbolo bajo la cabeza lectora/escritora. Si los dos primeros elementos del quíntuplo describen las condiciones actuales, entonces sus tres elementos finales indican las acciones que deben realizarse, escritas en orden de realización....
................
Una máquina Turing comienza con una cinta inicial y realiza una transformación en esa cinta. Si la máquina se detiene, el resultado de la transformación es el contenido de la cinta en el momento del detenimiento. Si la máquina nunca se detiene, el resultado no está definido. ( Kain 72, pp. 83-86)
En su artículo de 1936, A. M. Turing define la clase de máquinas abstractas que hoy llevan su nombre. Una máquina Turing es una máquina de estado finito asociada con una clase especial de ambiente –su cinta– en el cual puede guardar (y más tarde recobrar) secuencias de símbolos.... Son máquinas muy simples. En cada momento la parte que es una máquina de estado finito obtiene su estímulo de entrada mediante la lectura del símbolo escrito en cierto punto a lo largo de la cinta. La respuesta de la máquina puede cambiar tal símbolo y también mover la máquina una pequeña distancia en alguna de las dos direcciones a lo largo de la cinta. El resultado es que el estímulo para el nuevo ciclo de operación vendrá de un "cuadrado" distinto de la cinta, y la máquina puede así leer un símbolo que haya sido escrito ahí mucho antes. Esto significa que la máquina tiene acceso a una especie de memoria exterior rudimentaria, además de la que es suplida por su parte de estado finito. Y como no ponemos límite en la cantidad de cinta disponible, esta memoria tiene en efecto una capacidad infinita.... ( Minsky 67, p. 107)
Debemos considerar máquinas que tienen en cada momento solo una cantidad finita de estructura, pero que son capaces de ser extendidas indefinidamente conforme pasa el tiempo –"máquinas que crecen".... Así, en vez de una cinta infinita, necesitamos solamente una fábrica inexhaustible de cinta. ( Minsky 67, p. 116)
Una máquina Turing es una máquina de estado finito asociada con un almacén externo o memoria. Esta memoria tiene la forma de una secuencia de cuadrados, marcados en una cinta lineal. La máquina está acoplada a una cinta mediante una cabeza, situada en cada momento sobre algún cuadrado de la cinta. La cabeza tiene tres funciones, todas las cuales se ejercen en cada ciclo de operación de la máquina de estado finito. Estas funciones son leer el cuadrado de la cinta rastreado en ese momento, escribir en el cuadrado rastreado y mover la máquina a un cuadrado adyacente (que pasa a ser el cuadrado rastreado en el siguiente ciclo de operación). ( Minsky 67, p. 117)
Lo que está en la cinta cuando la máquina para dependerá de un modo complicado de lo que la cinta tenía al comenzar. Por eso podemos decir que el resultado de la computación presente en la cinta es una función de la entrada. Exactamente cuál función sea, eso dependerá, por supuesto, de la máquina Turing que se use. Entonces, podemos pensar que una máquina Turing define una función o la computa, o incluso que es una función. ( Minsky 67, p. 132)
Cuando la máquina arranca la cinta debe estar en blanco, excepto por un número finito de cuadrados....
................
Las partes de nuestras máquinas que son de estado finito pueden ser descritas muy bien por conjuntos de quíntuplos de la forma
(estado viejo, símbolo rastreado, estado nuevo, símbolo
escrito, dirección de movimiento)
....
en los cuales el tercero, el cuarto y el quinto símbolos quedan determinados por el primero y el segundo.... ( Minsky 67, p. 118-119)
Nuestro interés real en las máquinas Turing está en su uso como modelo para definir la computabilidad eficaz.
................
Podemos restringir nuestras máquinas al uso de dos símbolos
sin pérdida de generalidad.... Se puede mostrar también que
las máquinas Turing con cintas infinitas en ambas direcciones no
tienen ventaja o desventaja sobre máquinas con cintas infinitas
en solo una.... Podemos mostrar la equivalencia plegando las cintas
doblemente infinitas, y enseguida pareándolas con cuadrados alternos
de cintas infinitas simples.... (
Minsky
67, p. 129-130)
Existe una cierta máquina Turing que puede imitar el comportamiento de cualquier otra máquina Turing, dada una adecuada descripción de la estructura de esa otra máquina. (La descripción debe ser consignada en el ambiente-cinta, no tiene que ser incorporada en el alambrado de la máquina). ( Minsky 67, p. 112)
[Una máquina Turing capaz de simular cualquier otra máquina de la misma clase] es llamada máquina universal.... Para que una máquina fija pueda imitar a una máquina especificada arbitrariamente, necesita tener a su disposición dos cosas: una descripción de la máquina que debe simular y una descripción del contenido inicial de la cinta de esa máquina....
Podemos proveer una descripción completa de una máquina Turing enhebrando las ... representaciones de los quíntuplos que corresponden a tal máquina.... El orden en que los quíntuplos se enuncien no es importante. Sin embargo, debemos adoptar la convención de que el primer quíntuplo tendrá siempre como primer componente el estado inicial de la máquina....
La máquina universal debe ser una máquina fija, en el sentido de que tenga un número fijo de símbolos de cinta para trabajar. Esta máquina deberá ser capaz de imitar el comportamiento de cualquier máquina Turing de una sola cinta, incluso aquella que use muchos más símbolos de cinta que la misma máquina universal. Así pues, deben adoptarse algunas convenciones para codificar patrones arbitrarios de cinta mediante un alfabeto con símbolos fijos.... ( Hennie 77, pp. 90-93)
Para realizar sus computaciones, una máquina universal debe ser provista de dos cosas: una descripción de la máquina que debe simular y una descripción de la configuración inicial de su cinta. Como toda máquina puede ser representada por un conjunto ordenado de quíntuplos, y puesto que cada quíntuplo puede ser representado por una serie de ... [unos y ceros], las máquinas pueden ser descritas por hileras de ceros y unos.... ( Hennie 77, p. 103)
Los ejemplos de Turing de máquinas específicas eran ya
ejemplos del arte de programar; la máquina universal en particular
fue el primer ejemplo de un programa interpretativo. La máquina
universal proveyó también un modelo del "programa almacenado"
en el que los quíntuplos codificados en la cinta juegan el papel
de programa almacenado, y en el cual la máquina no hace ninguna
distinción fundamental entre "programa" y "datos".... (
Davis
58, pp. 158-160)
Dada una máquina Turing M que tiene en su cinta su propia descripción, ¿se detendrá M? ( Kain 72, p. 251)
Dada una descripción de una máquina (lista codificada de sus quíntuplos) y su descripción en un instante, ¿podemos decidir si parará? Debemos ser cuidadosos para definir lo que constituye una solución aceptable al problema.
Un problema es recursivamente insoluble si no existe una máquina Turing que contestará el problema para todos los posibles valores de sus parámetros. En este caso los parámetros son la descripción de la máquina y su descripción instantánea. La solución aceptable es una máquina H que acepte la descripción de una máquina arbitraria M y una descripción instantánea I de la configuración de M y diga si M se detendrá alguna vez si es puesta a trabajar a partir de la descripción instantánea. Pedimos que H se detenga cuando ha encontrado una decisión.
Ahora consideremos una versión restringida del problema.... Dada una máquina M, ¿se detendrá si recibe en su cinta su propia descripción? Si no podemos solucionar este problema restringido, no podremos resolver el problema general del detenimiento. ( Kain 72, pp. 117-118)
¿Qué pasa cuando una máquina (Turing universal) se enfrenta con su propia descripción? ... Encontramos que ciertas cuestiones que naturalmente preguntamos sobre máquinas no pueden contestarse, por lo menos no por un procedimiento eficaz para contestar preguntas. De hecho, los resultados más significativos [de la teoría computacional] son resultados negativos que indican limitaciones, no solo de los procedimientos eficaces mismos sino también de nuestra capacidad última para caracterizar, eficazmente, cuáles procedimientos son de hecho eficaces.
................
¿Cuáles computaciones mecánicas terminan eventualmente con un resultado definido y cuáles continúan para siempre sin una conclusión definida? Podemos mostrar, por medio de algunos trucos técnicos simples, que suponer la existencia de una máquina que puede contestar esta cuestión lleva a una contradicción; por lo tanto, ... ninguna máquina Turing puede contestar esta cuestión. Pero entonces, si aceptamos la tesis de Turing, no puede haber del todo ninguna manera eficaz de contestarla.... ( Minsky 67, p. 113)
Cuando una máquina Turing, con su cinta de entrada, es puesta en operación, puede transcurrir mucho, muchísimo tiempo antes de que complete su computación y se detenga. Para muchos pares máquina/cinta, ello nunca sucederá –la "computación" puede continuar eternamente–. Sería muy útil tener un procedimiento decisorio que nos permitiera, dada una máquina T y una cinta t, determinar si el proceso se detendrá algún día. [El término procedimiento decisorio, significa aquí un único conjunto de instrucciones, dado de una vez por todas, que nos facultara para resolver el problema del detenimiento para todo par máquina/cinta] ...¡[Pero] no puede haber ningún procedimiento eficaz que pueda hacer esto por nosotros! Está implícito en este argumento el compromiso de la tesis de Turing con la noción de que las computaciones de máquina Turing incluyen todos los procedimientos eficaces. Porque si suponemos que hay un procedimiento decisorio (el término siempre lleva la connotación de que el procedimiento es eficaz), entonces debe haber una máquina Turing que puede realizar el procedimiento.... ( Minsky 67, p. 146)
El problema decisorio de Hilbert: ¿existe un procedimiento mecánico para contestar todos los problemas matemáticos, dentro de alguna clase amplia pero bien definida? Turing encontró que podía expresar su versión de la cuestión en términos del problema de decidir si la nésima máquina de Turing podría de hecho llegar a detenerse cuando actuare sobre el número m. Este problema recibió el nombre de problema del detenimiento.... ( Penrose 89, p. 58)
¿Existe un procedimiento algorítmico para contestar la pregunta general el problema del detenimiento de modo completamente automático? Turing mostró que en verdad no existía ninguno. Su argumento fue esencialmente el siguiente. Supongamos primero que, por el contrario, existe tal algoritmo. Entonces, debe haber una máquina Turing H que "decide" si la nésima máquina de Turing, cuando actúa sobre el número m se detiene eventualmente. [Pero esto lleva a una contradicción, como puede verse fácilmente, cuando resulta que el número m es una descripción de la máquina H misma.] (Penrose 89, p. 59)
Al mostrar que no existe un algoritmo para decidir la cuestión del detenimiento de las máquinas Turing, Turing mostró (como Church, usando su propio tipo de enfoque bastante diferente) que no puede haber un algoritmo general para decidir las cuestiones matemáticas. ¡El problema decisorio de Hilbert no tiene solución!
Esto no quiere decir que en algún caso individual no podamos decidir la verdad, o lo contrario, de alguna cuestión matemática particular; o decidir si alguna máquina Turing se detiene o no. Por un ejercicio de ingenio, o incluso simplemente de sentido común, podemos decidir la cuestión en un caso dado. (Por ejemplo, si una lista de instrucciones en una máquina Turing no contiene la orden de detenerse, o contiene solo tales órdenes, entonces, el sentido común basta para decirnos si se detendrá o no). Pero no hay ningún algoritmo que funcione para todas las cuestiones matemáticas, ni para todas las máquinas Turing y todos los números sobre los que pueden actuar. ( Penrose 89, p. 63)
NOTA 1 Esta selección contiene párrafos escogidos de varios autores, ordenados de manera que su lectura resulte lo más comprensible posible. Indicamos entre paréntesis el nombre del autor y número(s) de página(s) de su obra de donde el párrafo se ha tomado. La referencia completa al autor y su obra debe consultarse en la bibliografía. Nota del editor.
NOTA 2
Hemos
variado los nombres de las variables originales para obtener más
fácil lectura de las fórmulas. Léanse así:
R = resultado o salida; I = insumo o entrada; E = estado interno. Nota
del editor.