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 Detalhes adicionais requeridos para visualizar ou implementar máquinas de Turing
2.1 Definições alternativas
2.2 O "estado"
3 Exemplo
4 Máquinas de Turing determinísticas e não-determinísticas
5 Máquinas de Turing universais
6 Comparação com máquinas reais
7 Máquinas de Turing físicas
8 História
8.1 Contexto histórico: máquinas computacionais
8.2 O Entscheidungsproblem (o "problema de decisão"): O décimo problema de Hilbert de 1900
8.3 Alan Turing uma-máquina(-automática)
8.4 1937-1970: O "computador digital", o nascimento da "ciência da computação"
8.5 1970-presente: a máquina de Turing como um modelo de computação
9 Ver também
10 Referências
11 Bibliografia
12 Ligações externas
Definição[editar | editar código-fonte]
Descrição informal[editar | editar código-fonte]
Uma máquina de Turing consiste em:
1. Uma fita que é dividida em células, uma adjacente à outra. Cada célula contém um símbolo de algum alfabeto finito. O alfabeto contém um símbolo especial branco (aqui escrito como ¬) e um ou mais símbolos adicionais. Assume-se que a fita é arbitrariamente