Questões de Concurso Público INMETRO 2010 para Pesquisador Tecnologista em Metrologia e Qualidade - Informática Aplicada à Metrologia Legal

A máquina de Turing capaz de simular outras máquinas de Turing é uma Turing completa, chamada máquina de Turing universal, capaz de calcular qualquer função recursiva, decidir qualquer linguagem recursiva e aceitar qualquer linguagem enumeravelmente recursiva.

Os autômatos finitos consistem na idealização de um computador capaz de acessar uma quantidade limitada de processos, o que restringe o processamento de informações de forma paralela; portanto, computadores desse gênero têm sua utilização limitada a aplicações simples, como, por exemplo, controlar elevadores ou portas automáticas.

Nos autômatos de pilha, existe uma estrutura de controle, que representa os estados e as funções de transição, e um input, que o autômato lê da esquerda para a direita, uma casa de cada vez, atualizando a estrutura de controle.

Os autômatos de pilha são modelos com uma quantidade de memória finita. Por sua vez, um autômato finito, apesar da limitada capacidade de processamento, por meio de uma pilha, consegue acessar a uma quantidade infinita de memória.

Os autômatos de pilha correspondem a um modelo mais poderoso que as máquinas de Turing, visto que permitem fazer várias operações pop sem perder informações.