Máquina de Turing
O modelo que define o que é "computável"
Em 1936, o matemático Alan Turing propôs um modelo de máquina extremamente simples — tão simples que parece até ingênuo — para responder uma pergunta bem mais profunda: o que, exatamente, pode ser calculado por um procedimento mecânico? Esse modelo, hoje chamado Máquina de Turing, não é um projeto de hardware — é um experimento mental. E é a base teórica por trás de qualquer computador real que já foi construído, incluindo os computadores quânticos.
As peças do modelo
- Fita: uma fita infinita dividida em células, cada uma guardando um símbolo (por exemplo,
0,1ou "branco"). - Cabeça de leitura/escrita: fica sobre uma célula por vez, pode ler o símbolo, escrever um novo símbolo, e mover-se uma célula para a esquerda ou direita.
- Estado: a máquina está sempre em um "estado" (uma situação interna), e muda de estado conforme uma tabela de regras.
- Tabela de transições: para cada combinação de (estado atual, símbolo lido), a tabela diz o que fazer: qual símbolo escrever, para qual lado mover a cabeça, e para qual estado ir a seguir.
Simulador Interativo da Máquina de Turing
Experimente o simulador abaixo para acompanhar a fita e a cabeça de leitura passo a passo em tempo real:
Simulador da Máquina de Turing
Exemplo: incrementar um número binário
O diagrama acima é a tabela de transições completa de uma máquina de Turing que faz uma única coisa: soma 1 a um número binário escrito na fita. A ideia é a mesma "vai um" que você usa na soma decimal — só que em base 2, todo 1 + 1 vira 0 e carrega 1 para a próxima casa.
A cabeça começa no bit mais à direita (o menos significativo), no estado CARREGAR:
- Fita: 1 0 1 1 (cabeça no último bit) — lê 1 → escreve 0, move para a esquerda. Continua em
CARREGAR. - Fita: 1 0 1 0 — lê 1 → escreve 0, move para a esquerda. Continua em
CARREGAR. - Fita: 1 0 0 0 — lê 0 → escreve 1, e para.
- Resultado final: 1 1 0 0.
1011 em binário é 11 em decimal; o resultado 1100 é 12 — exatamente 11 + 1. Três regras simples (lê 1 → escreve 0 e continua; lê 0 → escreve 1 e para) foram suficientes para "calcular" uma soma.
Por que isso importa
A Máquina de Turing prova algo poderoso: qualquer coisa que qualquer computador — do primeiro computador eletromecânico ao supercomputador mais avançado, passando pelo seu celular — consegue calcular, uma Máquina de Turing também consegue calcular (dado tempo e fita suficientes). Essa ideia é conhecida como tese de Church-Turing. Ela não diz que todo computador é uma máquina de Turing fisicamente — diz que nenhum computador real consegue calcular mais do que uma máquina de Turing consegue, em princípio. É por isso que, quando alguém diz que uma linguagem de programação ou um sistema é "Turing completo", está dizendo que ele consegue expressar qualquer computação que uma Máquina de Turing conseguiria.
A Máquina de Turing responde o que é possível computar. Ela não diz nada sobre como construir uma máquina real, com componentes elétricos, que faça isso de forma prática e rápida — essa é a pergunta que a Arquitetura de Von Neumann responde.