Modelo de turing

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 é chamado 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, é inexcedí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 é inexcedí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