A máquina de Turing: o modelo abstrato que define a computação
Compreenda a máquina de Turing, a sua fita, estados, cabeça de leitura e escrita e o seu papel na definição dos algoritmos e dos limites da computação.
Publicado 31 de julho de 2026Atualizado 7 de agosto de 2026Leitura : 11 minPor Yann Bastien
A máquina de Turing é um dos conceitos mais importantes da informática teórica. No entanto, quase nada tem a aparência de um computador moderno: não possui ecrã, processador ou teclado e, na sua forma teórica, nem sequer existe um limite real para a memória.
Imaginada por Alan Turing em 1936, responde a uma pergunta muito mais fundamental: o que é uma computação? Turing concebe uma máquina deliberadamente mínima, capaz de ler e escrever símbolos numa fita seguindo regras precisas.
Apesar da sua extrema simplicidade, o modelo é suficientemente poderoso para representar qualquer cálculo executável por um algoritmo segundo a conceção clássica da computabilidade. Permite compreender o que é um algoritmo, o que um computador pode teoricamente calcular e por que razão certos problemas permanecem impossíveis de resolver automaticamente, independentemente da potência das máquinas futuras.
Por que era necessário definir a computação?
No início do século XX, os matemáticos procuravam formalizar os fundamentos da sua disciplina. O Entscheidungsproblem de David Hilbert perguntava, de forma simplificada, se poderia existir um procedimento mecânico capaz de determinar, para qualquer proposição de um sistema lógico, se esta é demonstrável.
Mas o que significa exatamente «seguir um procedimento mecânico»? Em 1936, o computador eletrónico programável ainda não existia. Era necessário definir matematicamente um procedimento de cálculo independentemente de qualquer máquina real. É precisamente isso que Turing faz. A biografia de Alan Turing apresenta o contexto mais amplo do seu percurso.
Uma máquina deliberadamente muito simples
Uma máquina de Turing clássica possui apenas alguns elementos:
uma fita dividida em células;
um conjunto limitado de símbolos;
uma cabeça de leitura e escrita;
um conjunto finito de estados;
uma tabela de regras de transição.
Em cada etapa, a máquina observa o símbolo sob a cabeça. De acordo com esse símbolo e com o estado atual, uma regra indica se deve escrever um símbolo, deslocar-se uma célula para a esquerda ou para a direita, mudar de estado e eventualmente parar. Depois, o processo recomeça.
Uma sucessão de ações elementares pode assim produzir um cálculo complexo.
A fita: memória teoricamente ilimitada
A fita é representada como uma sequência de células, cada uma podendo conter um símbolo de um alfabeto definido. No modelo teórico, assume-se que existe fita suficiente para a máquina não ficar sem memória durante o cálculo em estudo.
Isto não significa que um computador real possa ter memória infinita. A hipótese separa duas perguntas: um problema é teoricamente computável? E dispomos de recursos físicos suficientes para executar realmente o cálculo? A máquina de Turing interessa-se sobretudo pela primeira.
A cabeça de leitura e escrita e os estados
A cabeça observa apenas uma célula de cada vez. Pode ler o símbolo presente, substituí-lo e deslocar-se. A máquina possui também um estado atual, por exemplo q0, q1 ou q2.
Uma regra pode indicar: se a máquina estiver em q0 e ler 1, escreve 0, desloca-se para a direita e passa a q1.
O comportamento completo é portanto determinado por estado atual + símbolo lido + regra de transição.
Um exemplo simples: adicionar 1
Representemos o número 4 em unário por quatro símbolos 1:
1111
Queremos adicionar 1. Enquanto a cabeça lê 1, desloca-se para a direita; quando encontra uma célula vazia, escreve 1 e para.
11111
A máquina calculou 4 + 1 = 5. Nenhum computador moderno faria uma adição desta forma. O exemplo mostra apenas que um cálculo pode ser decomposto numa sequência de regras mecânicas perfeitamente determinadas.
Uma máquina de Turing é um computador real?
Não no sentido habitual. É antes de tudo um objeto matemático. Em 1936, Turing não pretendia propor o projeto industrial de um computador, mas obter um modelo preciso para raciocinar sobre procedimentos computáveis.
No século XIX, Babbage pergunta como engenheiro: como construir uma máquina geral capaz de executar cálculos diferentes? Os cartões perfurados deveriam representar operações e dados.
Turing coloca uma pergunta mais abstrata: o que pode uma máquina de cálculo fazer em princípio? As abordagens são diferentes, mas ambas participam na separação progressiva entre a máquina física e as instruções que determinam o seu comportamento.
A máquina universal
Uma das ideias mais poderosas de Turing é a máquina universal. Uma máquina particular pode receber na fita a descrição de outra máquina e os dados sobre os quais esta deve trabalhar, e depois simular o seu funcionamento.
Assim, cada tarefa não necessita de uma máquina física própria.
Uma máquina, muitos programas
Hoje, isto parece natural. O mesmo computador pode apresentar uma página Web, editar uma fotografia, executar um jogo, processar um ficheiro CSV, compilar código ou reproduzir vídeo. Não reconstruímos o computador para cada tarefa: mudamos o programa.
A máquina universal formaliza esta separação entre um dispositivo geral e a descrição do cálculo a executar.
Máquina universal e arquitetura de von Neumann não são a mesma coisa
A máquina universal de Turing é um modelo matemático que mostra que uma máquina pode simular outras máquinas. A arquitetura de von Neumann descreve uma organização prática dos computadores eletrónicos em que instruções e dados podem ser guardados na memória.
As ideias são intelectualmente próximas, mas respondem a objetivos diferentes: Turing estuda a computabilidade; os criadores dos primeiros computadores eletrónicos tratam também da arquitetura e realização prática.
O que é um problema computável?
De forma simplificada, um problema é computável se existir uma máquina de Turing capaz de produzir o resultado esperado num número finito de etapas para as entradas consideradas.
Uma intuição - «deve existir um método» - torna-se assim uma questão matemática: podemos descrever um procedimento preciso? Pode ser expresso por regras mecânicas? Terminará com uma resposta? Estas questões estão no centro da teoria da computabilidade.
Nem todos os problemas são computáveis
Uma das conclusões mais importantes de Turing é contraintuitiva: existem problemas que nenhum algoritmo consegue resolver em todos os casos. Não é uma limitação temporária dos computadores da década de 1930, nem desaparece com processadores mais rápidos ou mais memória.
O exemplo mais conhecido é o problema da paragem.
O problema da paragem
Imaginemos um programa HALT que recebe um programa qualquer e os respetivos dados e deve responder: este programa acabará por parar ou continuará indefinidamente?
Para alguns programas, a resposta é simples. Mas queremos que HALT funcione para absolutamente todos os programas possíveis e todas as entradas. Turing demonstra que um algoritmo universal deste tipo não pode existir.
Por que é tão importante?
O resultado revela um limite fundamental da automatização. As ferramentas de análise de código podem detetar muitos problemas, reconhecer determinados ciclos ou provar propriedades para certas categorias de programas. Mas nenhuma ferramenta consegue resolver perfeitamente o problema da paragem para todos os programas possíveis.
A diferença entre «muito difícil» e «impossível em geral» é fundamental.
Um limite independente do hardware
Mesmo computadores mil milhões de vezes mais rápidos, memória gigantesca ou uma máquina ideal não tornariam decidível o problema da paragem.
Podemos distinguir pelo menos três tipos de limites: tempo, memória e computabilidade. Os dois primeiros dizem respeito aos recursos necessários; o terceiro, à própria existência de um algoritmo geral.
Computabilidade e complexidade
A computabilidade pergunta: existe um algoritmo capaz de resolver este problema? A complexidade algorítmica pergunta: se existe, quanto tempo ou memória necessita?
Um problema pode ser computável mas extremamente dispendioso. Um problema indecidível, pelo contrário, não possui um algoritmo geral que forneça sempre a resposta correta.
Alonzo Church e o cálculo lambda
Alonzo Church desenvolveu independentemente o cálculo lambda, outro formalismo para representar cálculos. Embora pareçam muito diferentes, o cálculo lambda e as máquinas de Turing caracterizam a mesma classe de funções computáveis.
Esta convergência de modelos independentes é particularmente importante.
A tese de Church-Turing
De forma simplificada: todo o cálculo realizável por um procedimento efetivo pode ser executado por uma máquina de Turing.
É uma tese e não um teorema matemático comum, porque «procedimento efetivo» é originalmente uma noção intuitiva. A sua força é reforçada pelo facto de muitos modelos de cálculo posteriores se revelarem equivalentes em poder computacional.
Um computador moderno é uma máquina de Turing?
Não literalmente. Possui memória limitada, uma arquitetura muito mais complexa, processadores, caches, periféricos e por vezes vários núcleos. Mas, para estudar o que é computável em princípio, os computadores generalistas clássicos são considerados equivalentes ao modelo de Turing sob as hipóteses teóricas habituais sobre recursos.
Mudar de processador ou linguagem pode tornar um cálculo mais rápido, mas não desloca subitamente a fronteira fundamental da computabilidade.
A linguagem de programação muda o que é computável?
Python, Java, C, JavaScript ou C++ têm sintaxes, abstrações, desempenho e ecossistemas muito diferentes. Uma linguagem generalista Turing-completa pode, em teoria e com recursos suficientes, expressar qualquer cálculo executável por uma máquina de Turing.
O poder teórico de computação é apenas uma das muitas dimensões de uma linguagem.
O que é a completude de Turing?
Um sistema é geralmente dito Turing-completo quando possui capacidades suficientes para simular uma máquina de Turing universal, sob as hipóteses teóricas habituais de memória. A expressão é usada para linguagens de programação, máquinas virtuais, sistemas de reescrita e até certos jogos ou programas.
Ser Turing-completo não significa ser rápido, prático ou concebido para programação. Significa essencialmente possuir poder expressivo suficiente para computação geral.
Uma máquina extremamente simples pode ser universal
Não são necessárias centenas de instruções diferentes para obter universalidade. Variantes muito simples de máquinas de Turing podem ser universais. Comportamentos sofisticados podem emergir da combinação repetida de um pequeno conjunto de operações elementares.
Dados e instruções tornam-se informação
Numa máquina universal, a descrição da máquina a simular é representada sob a forma de símbolos. As instruções tornam-se dados que a máquina pode ler.
Textos, números, imagens, programas e instruções podem ser representados numa forma manipulável por uma máquina. O artigo sobre a teoria da informação explora outra faceta desta abstração: como a informação pode ser medida e codificada.
A máquina de Turing não descreve o desempenho de um computador
O seu principal objetivo não é comparar velocidades. Uma máquina de Turing pode executar um cálculo de forma incrivelmente lenta em comparação com um computador real. A pergunta central é: este cálculo pode ser executado por um procedimento algorítmico?
Para saber se uma solução é útil na prática, é necessário estudar depois a complexidade, os algoritmos e a arquitetura real.
E os computadores quânticos?
Os computadores quânticos podem oferecer vantagens consideráveis para certas categorias de problemas e utilizam princípios físicos diferentes. No quadro teórico habitual, porém, não tornam computáveis problemas que são fundamentalmente não computáveis no sentido de Turing.
Podem alterar a eficiência de determinados cálculos, não necessariamente a fronteira fundamental entre computável e não computável.
Por que se continua a ensinar a máquina de Turing?
Uma fita abstrata pode parecer distante do desenvolvimento de software em 2026. No entanto, o modelo permite compreender ideias fundamentais:
o que é realmente um algoritmo;
a diferença entre programa e máquina;
a noção de computação universal;
a existência de problemas indecidíveis;
a diferença entre computabilidade e complexidade;
os fundamentos teóricos das linguagens de programação.
Tal como certos modelos idealizados da física, simplifica deliberadamente a realidade para tornar visíveis os princípios fundamentais.
Da máquina de Turing aos computadores modernos
A máquina de Turing de 1936 não é diretamente a arquitetura dos nossos computadores. Babbage imaginou uma máquina mecânica programável; os cartões perfurados mostraram que instruções e dados podiam ser representados num suporte externo; Turing formalizou uma máquina universal; nos anos 1940, os computadores eletrónicos de programa armazenado transformaram progressivamente estas ideias em sistemas físicos.
A arquitetura de von Neumann tornou-se depois um dos modelos mais influentes para organizar concretamente processador, memória, dados e instruções. Estas etapas não formam uma linha reta e resultam do trabalho de muitos investigadores.
Um legado ainda presente
Quase noventa anos depois do artigo de Turing, o modelo continua no centro da informática teórica. Sempre que perguntamos se um problema pode ser automatizado, se um programa pode analisar perfeitamente todos os outros programas, se uma linguagem pode expressar cálculos gerais ou quais são os limites intrínsecos dos algoritmos, regressamos direta ou indiretamente à teoria da computabilidade.
Os computadores mudaram de forma espetacular, mas mais potência não elimina os limites matemáticos do cálculo.
A reter
A máquina de Turing é um modelo matemático da computação proposto por Alan Turing em 1936. Baseia-se numa fita, numa cabeça de leitura e escrita, símbolos, estados e regras de transição.
A máquina universal mostra que uma só máquina pode simular muitas outras quando recebe a respetiva descrição como dados. O problema da paragem mostra, por outro lado, que não existe um algoritmo universal capaz de decidir para todos os programas se estes acabarão por parar.
A máquina de Turing ensina-nos assim duas coisas aparentemente opostas: uma máquina muito simples pode realizar uma enorme variedade de cálculos, mas nenhuma máquina algorítmica pode calcular tudo.
Perguntas frequentes
Quem inventou a máquina de Turing?
O matemático britânico Alan Turing propôs o modelo no artigo de 1936 On Computable Numbers, with an Application to the Entscheidungsproblem.
Foi realmente construída uma máquina de Turing?
O conceito original é um modelo matemático, não o projeto de um computador. Mais tarde foram construídos modelos físicos para fins pedagógicos.
O que é a fita de uma máquina de Turing?
É a memória teórica do modelo: uma sequência de células que podem conter símbolos e ser lidas ou alteradas pela cabeça.
O que é uma máquina de Turing universal?
É uma máquina capaz de ler a descrição de outra máquina de Turing e os seus dados de entrada e depois simular o respetivo comportamento.
O que é o problema da paragem?
Pergunta se um algoritmo geral pode decidir, para qualquer programa e entrada, se o programa acabará por parar. Turing demonstrou que tal algoritmo não pode existir.
Os computadores modernos são Turing-completos?
Os computadores generalistas modernos e a maioria das linguagens generalistas são considerados Turing-completos em sentido teórico, sob as hipóteses habituais sobre memória disponível.
Os computadores quânticos ultrapassam os limites da máquina de Turing?
Podem resolver alguns problemas computáveis de forma muito mais eficiente, mas, no entendimento teórico habitual, não tornam computáveis problemas fundamentalmente não computáveis.
Descubra Alan Turing, o seu trabalho sobre computabilidade, o papel em Bletchley Park, os projetos de computadores e o contributo fundador para a inteligência artificial.
