Voltar aos artigos
Quem foi Alan Turing?
Alan Turing foi um matemático britânico considerado o pai da computação moderna. Em 1936, criou o conceito de Máquina de Turing, base teórica dos computadores. Durante a Segunda Guerra Mundial, ajudou a decifrar os códigos da máquina Enigma, contribuindo decisivamente para a vitória dos Aliados.
Em 1950, propôs o Teste de Turing, que avalia se uma máquina pode se comportar como um ser humano — referência até hoje na área de inteligência artificial.
Apesar de suas contribuições, foi condenado por ser homossexual em 1952, e morreu dois anos depois, em circunstâncias trágicas. Hoje, é reconhecido como herói de guerra e ícone da ciência, com seu rosto estampando a nota de £50 no Reino Unido.
O que é uma Máquina de Turing?
A Máquina de Turing é um modelo teórico de computador criado por Alan Turing em 1936. Ela descreve uma máquina simples capaz de ler e escrever símbolos em uma fita infinita, seguindo um conjunto de regras.
Apesar de abstrata, essa ideia é poderosa: provou que certos problemas podem (ou não) ser resolvidos por algoritmos. Em outras palavras, a Máquina de Turing define os limites do que é computável.
Ela é a base da ciência da computação e inspirou o funcionamento dos computadores modernos. Até hoje, serve como referência para entender linguagens de programação, algoritmos e inteligência artificial.
Exercícios Resolvidos: Máquinas de Turing
A seguir, apresento um conjunto de exercícios resolvidos que ilustram a construção de Máquinas de Turing para decidir linguagens formais. A primeira imagem de exercício resolvido mostra, por exemplo, uma máquina que decide a linguagem:
ou seja, o conjunto de palavras binárias que são palíndromos — iguais ao seu próprio reverso.
Uma Máquina de Turing funciona com base em três elementos fundamentais:
- Fita infinita dividida em células, que armazena símbolos e pode ser lida ou modificada;
- Cabeça de leitura/gravação, que se move para a esquerda ou direita a cada passo;
- Conjunto de estados, com uma função de transição que define o comportamento da máquina.
A regra de transição é determinada por uma tripla:
(símbolo lido, símbolo a escrever, direção do movimento)
com base no estado atual. Por exemplo, no diagrama da imagem, a transição:
1, ␣, →
significa que, ao ler o símbolo 1, a máquina escreve o símbolo branco (␣, indicando espaço vazio), move a cabeça para a direita e entra no próximo estado indicado.
A máquina aceita a entrada se alcançar um estado final de aceitação (marcado com Y nas imagens), e rejeita se cair em um estado de rejeição (N) ou entrar em um ciclo sem saída. Esse tipo de formalismo é essencial para entender o que significa “decidir” uma linguagem no contexto da Teoria da Computação.
Nos exemplos seguintes, você verá como outras linguagens podem ser decididas com construções semelhantes.
Originalmente publicado em 08/10/2019
