¿Qué es una máquina abstracta?

Las máquinas abstractas, también llamadas autómatas, son un elemento de la informática teórica. Una máquina abstracta se asemeja a una función en matemáticas. Recibe entradas y produce salidas de acuerdo con las reglas especificadas. Las máquinas abstractas difieren de las máquinas más literales porque se supone que funcionan de manera perfecta e independiente del hardware. Se subdividen en tipos sobre la base de características, como cómo realizan sus operaciones y qué tipos de entradas pueden recibir.

Al clasificar las máquinas abstractas, una de las distinciones más simples se refiere a la cantidad de operaciones que están permitidas en cualquier punto dado. Una máquina abstracta se llama determinista si siempre hay solo una forma en que continúe. No es determinista si existen múltiples posibilidades para la máquina en al menos uno de sus posibles estados. Un automatón de "empuje" es uno que tiene la capacidad de manipular su pila de entradas, en lugar de simplemente responderles uno por one en el orden en que aparecen.

Wolfram Mathworld da dos ejemplos famosos de máquinas abstractas. Uno de estos ejemplos es el juego de la vida de Conway, que es una máquina abstracta determinista porque solo una configuración puede salir de cualquier otra. Este juego usa una cuadrícula en la que cada caja, o celda, puede tener el estado "vivo" o "muerto". El estado de toda la cuadrícula se determina sobre la base del estado anterior. Si una celda viva toca exactamente otras dos o tres células vivas, continúa viviendo. Si tiene uno, dos o más de tres vecinos (hasta ocho posibles), muere. Una celda muerta con exactamente tres vecinos cobrará vida; de lo contrario, permanecerá muerto.

Otro ejemplo, la máquina Turing, es una de las máquinas abstractas más básicas y fundamentales de la informática. Una máquina Turing realiza operaciones en una cinta, una cadena de símbolos.de tamaño ilimitado. Contiene instrucciones tanto para cambiar los símbolos como para cambiar el símbolo sobre el que está funcionando. Una simple máquina de Turing podría tener solo la instrucción "Transformar el símbolo en 1, luego moverse a la derecha". Esta máquina no generaría más que una cadena de 1. Esta simple máquina Turing es determinista, pero también es posible construir máquinas de Turing no deterministas que puedan realizar varias operaciones diferentes dada la misma entrada.

Estas máquinas abstractas pueden cumplir muchos propósitos. Pueden ser juguetes teóricos divertidos, pero también pueden servir como modelos para sistemas informáticos reales. La máquina abstracta está en el corazón de la informática como disciplina.