Máquina de Turing é

A máquina de Turing é um dispositivo teórico, conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936). Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições) e não à sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital.

Turing também se envolveu na construção de máquinas físicas para quebrar os códigos secretos das comunicações alemãs durante a II Guerra Mundial, tendo utilizado alguns dos conceitos teóricos desenvolvidos para o seu modelo de computador universal.




Índice [esconder]
1 Definição
1.1 Descrição informal
1.2 Definição formal
1.2.1 Máquina de Turing com uma fita
1.2.2 Máquina de Turing com k fitas
2 Exemplo
3 Máquinas de Turing determinísticas e não-determinísticas
4 Máquinas de Turing universais
5 Comparação com máquinas reais
6 Máquina de Turing física
7 Ver também
8 Referências
9 Ligações externas
9.1 Simuladores