O que é uma máquina abstrata?
Máquinas abstratas, também chamadas de autômatos, são um elemento da ciência da computação teórica. Uma máquina abstrata se assemelha a uma função na matemática. Ele recebe entradas e produz saídas de acordo com as regras especificadas. Máquinas abstratas diferem de máquinas mais literais porque se supõe que funcionem perfeita e independentemente do hardware. Eles são subdivididos em tipos com base em características como, por exemplo, como executam suas operações e que tipos de insumos podem receber.
Ao classificar as máquinas abstratas, uma das distinções mais simples diz respeito ao número de operações que eles têm permissão para realizar em qualquer ponto. Uma máquina abstrata é chamada determinística se houver sempre apenas uma maneira de prosseguir. Não é determinístico se existem várias possibilidades para a máquina em pelo menos um de seus estados possíveis. Um autômato "pushdown" é aquele que tem capacidade de manipular sua pilha de entradas, em vez de simplesmente responder a elas uma a uma na ordem em que aparecem.
Wolfram MathWorld dá dois exemplos famosos de máquinas abstratas. Um desses exemplos é o jogo da vida de Conway, que é uma máquina abstrata determinística porque apenas uma configuração pode emergir de qualquer outra. Este jogo usa uma grade na qual cada caixa ou célula pode ter o estado "vivo" ou "morto". O estado de toda a grade é determinado com base no estado anterior. Se uma célula viva toca exatamente duas ou três outras células vivas, ela continua viva. Se tiver um, dois ou mais de três vizinhos (até oito possíveis), ele morre. Uma célula morta com exatamente três vizinhos ganhará vida; caso contrário, ele permanecerá morto.
Outro exemplo, a máquina de Turing, é uma das máquinas abstratas mais básicas e fundamentais da ciência da computação. Uma máquina de Turing realiza operações em uma fita - uma sequência de símbolos - de tamanho ilimitado. Ele contém instruções para alterar os símbolos e para alterar o símbolo no qual está operando. Uma simples máquina de Turing pode ter apenas a instrução "transformar símbolo em 1 e depois mover para a direita". Esta máquina não produziria nada além de uma sequência de 1s. Essa máquina de Turing simples é determinística, mas também é possível construir máquinas de Turing não determinísticas que podem executar várias operações diferentes, com a mesma entrada.
Essas máquinas abstratas podem servir a muitos propósitos. Eles podem ser divertidos brinquedos teóricos, mas também podem servir de modelo para sistemas de computador reais. A máquina abstrata está no coração da ciência da computação como disciplina.