¿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 perfectamente e independientemente del hardware. Se subdividen en tipos en función de características tales 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 al número de operaciones que se les permite realizar en un punto dado. Una máquina abstracta se llama determinista si siempre hay una sola forma de proceder. No es determinista si existen múltiples posibilidades para la máquina en al menos uno de sus posibles estados. Un autómata "pushdown" es aquel que tiene la capacidad de manipular su pila de entradas, en lugar de simplemente responderlas una por una en el orden en que aparecen.

Wolfram MathWorld ofrece 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 surgir de otra. Este juego utiliza una cuadrícula en la que cada casilla 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 célula viva toca exactamente otras dos o tres células vivas, continúa viva. Si tiene uno, dos o más de tres vecinos (hasta un posible ocho), muere. Una celda muerta con exactamente tres vecinos cobrará vida; de lo contrario, permanecerá muerto.

Otro ejemplo, la máquina de Turing, es una de las máquinas abstractas más básicas y fundamentales en informática. Una máquina de 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á operando. Una máquina de Turing simple 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 de Turing es determinista, pero también es posible construir máquinas de Turing no deterministas que pueden realizar varias operaciones diferentes con la misma entrada.

Estas máquinas abstractas pueden servir para muchos propósitos. Pueden ser divertidos juguetes teóricos, 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.