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 em matemática. Ele recebe entradas e produz saídas de acordo com regras especificadas. As máquinas abstratas diferem de máquinas mais literais porque se supõe que funcionem perfeitamente e independentemente do hardware. Eles são subdivididos em tipos com base em características, como como executam suas operações e que tipos de entradas podem receber. Uma máquina abstrata é chamada determinística se sempre houver apenas uma maneira de prosseguir. É não determinístico se houver várias possibilidades para a máquina em pelo menos um de seus estados possíveis. Um autômato "pushdown" é aquele que tem a capacidade de manipular sua pilha de insumos, em vez de simplesmente responder a eles um por One na ordem em que eles aparecem.
Wolfram Mathworld fornece dois exemplos famosos de máquinas abstratas. Um desses exemplos é o jogo de 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, continua a viver. Se tiver um, dois ou mais de três vizinhos (até um possível oito), ele morre. Uma célula morta com exatamente três vizinhos ganhará vida; caso contrário, 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 executa operações em uma fita - uma série de símbolos -de tamanho ilimitado. Ele contém instruções tanto para alterar os símbolos quanto para alterar o símbolo sobre o qual está operando. Uma máquina de Turing simples pode ter apenas a instrução "Transforme o símbolo em 1 e depois se mova para a direita". Esta máquina emitiria nada além de uma sequência de 1. Esta 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, dada a mesma entrada.
Essas máquinas abstratas podem servir a muitos propósitos. Eles podem ser brinquedos teóricos divertidos, mas também podem servir como modelos para sistemas de computador reais. A máquina abstrata está no coração da ciência da computação como uma disciplina.