Máquina de Turing universal
Origem: Wikipédia, a enciclopédia livre.
Toda Máquina de Turing computa uma certa função computável parcial a partir da cadeia dada formada pelos símbolos do alfabeto. Neste sentido ela comporta-se como um computador com um programa fixo. No entanto, como Alan Turing descreveu, podemos codificar a tabela de ação de qualquer máquina de Turing em uma cadeia de símbolos. Portanto podemos tentar construir uma máquina de Turing que espera em sua fita uma cadeia descrevendo a tabela de ação seguida por uma cadeia descrevendo a fita de entrada, e então computa a fita que a máquina de Turing codificada teria computado.
Como Turing mostrou, tal máquina de Turing é de fato possível e, como é capaz de simular outras máquinas de Turing, ela é chamada de máquina de Turing universal.
Com essa codificação de tabelas de ação como cadeias, torna-se possível, a princípio, que máquinas de Turing respondam questões sobre o comportamento de outras máquinas de Turing. Muitas dessas questões, no entanto, são indecidíveis, o que significa que a função em questão não pode ser calculada por nenhuma máquina de Turing.
Por exemplo, Turing mostrou em seu artigo original que o problema de determinar se uma máquina de Turing em particular vai parar para uma entrada dada (ou para qualquer entrada), conhecido como Problema da parada, é indecidível. O teorema de Rice mostra que qualquer questão não-trivial sobre o comportamento ou saída de uma máquina de Turing é indecidível.
Se expandirmos a definição para incluir qualquer máquina de Turing que simule algum modelo computacional Turing-completo (e não apenas máquinas de Turing que simulam diretamente outras máquinas de Turing), então uma máquina de Turing universal pode ser bem simples, usando apenas alguns estados e alguns símbolos. Por exemplo, apenas 2 estados são necessários, uma vez que uma máquina universal 2×18 (com 2 estados e 18 símbolos) é conhecida. Uma lista completa das menores máquinas de Turing universais conhecidas é: 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. Elas simulam um modelo computacional chamado tag systems.
Uma máquina de Turing universal é Turing-completa. Ela pode calcular qualquer função recursiva, decidir qualquer linguagem recursiva e aceitar qualquer linguagem enumeravelmente recursiva. De acordo com a tese de Church-Turing, os problemas solucionáveis por uma máquina de Turing universal são exatamente aqueles problemas solucionáveis por um algoritmo ou um procedimento efetivo de computação, para qualquer definição razoável destes termos.
| Teoria de Autômatos: Linguagem formal e gramática formal | |||
|---|---|---|---|
| Hierarquia Chomsky |
Gramática | Linguagem | Reconhecedor |
| Tipo-0 | Estrutura de frase | Recursivamente enumerável | Máquina de Turing |
| -- | Estrutura de frase | Recursiva | Máquina de Turing |
| Tipo-1 | Sensíveis ao contexto | Sensíveis ao contexto | Máquina de Turing com memória limitada |
| Tipo-2 | Livre de contexto | Livre de contexto | Autômato com pilha |
| Tipo-3 | Regular | Regular | Autômato finito |
