Las máquinas abstractas, también llamadas autómatas, son un elemento de la informática teórica. Una máquina abstracta se parece a una función en matemáticas. Recibe entradas y produce salidas de acuerdo con reglas especificadas. Las máquinas abstractas se diferencian de las máquinas más literales porque se supone que funcionan perfectamente e independientemente del hardware. Se subdividen en tipos sobre la base de características tales como cómo realizan sus operaciones y qué tipos de insumos 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 responder a ellas 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 cualquier 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 red 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 ocho posibles), 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 de la 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á funcionando. Una máquina de Turing simple puede tener solo la instrucción «transformar el símbolo en 1, luego mover a la derecha». Esta máquina no produciría nada más que una cadena de unos. 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.