| No estado | Lê | Escreve | Move-se | Estado seguinte |
|---|
Simulador de máquina de Turing
Uma máquina de Turing é o computador mais simples possível: uma cabeça que lê um símbolo de uma fita infinita, escreve um símbolo, move-se uma célula para a esquerda ou para a direita e muda de estado, seguindo uma pequena tabela de regras. Alan Turing inventou-a em 1936, e tudo o que o seu computador faz poderia, em princípio, ser feito desta forma. Escreva as suas próprias regras ou carregue um exemplo, prima Executar e veja a fita mudar passo a passo, com um diagrama de toda a sua história por baixo. Escolha um programa ou escreva o seu, introduza a entrada e prima Executar, ou Passo para seguir uma regra de cada vez; Recuar desfaz um passo. Cada linha do programa é uma regra: estado, símbolo lido, símbolo a escrever, movimento (L, R ou N para não mover) e estado seguinte, por exemplo A 0 -> 1 R B. Use _ para uma célula vazia. A máquina começa no estado da primeira regra, sobre o primeiro símbolo da entrada, e para em H, accept ou reject, ou quando nenhuma regra se aplica. O diagrama mostra a fita depois de cada passo, de cima para baixo.
Como funciona
- Escolha um programa de exemplo ou escreva regras como A 0 -> 1 R B, uma por linha, e escreva a entrada.
- Prima Executar para ver a cabeça mover-se, ou Passo para seguir uma regra de cada vez; Recuar desfaz um passo.
- Leia o estado, os passos e os símbolos na fita nos quadros, e a história da fita no diagrama.
Como funciona a máquina
Em cada momento, a máquina está num de poucos estados e a sua cabeça está sobre uma célula da fita. A regra para esse estado e para o símbolo sob a cabeça diz três coisas: que símbolo escrever na célula, se deve mover-se para a esquerda, para a direita ou não se mover, e para que estado passar a seguir. É a máquina inteira. Para quando chega a um estado de paragem, como H, accept ou reject, ou quando nenhuma regra se aplica. Um programa que soma 1 a um número binário precisa apenas de nove regras destas.
Castores atarefados
Que máquina com n estados, iniciada numa fita vazia, escreve o maior número de uns antes de parar? Tibor Radó colocou esta pergunta em 1962. As campeãs chamam-se castores atarefados e crescem mais depressa do que qualquer função que um computador consiga calcular. Dois estados dão 4 uns em 6 passos, três estados 6 uns, quatro estados 13 uns em 107 passos. A campeã de cinco estados, encontrada em 1989, escreve 4098 uns em 47 176 870 passos, e em 2024 uma colaboração online provou, com matemática verificada por computador, que nenhuma outra máquina de cinco estados que pare funciona durante mais tempo.
Perguntas frequentes
Como escrevo uma regra?
Uma regra por linha: o estado atual, o símbolo que lê, o símbolo a escrever, o movimento (L, R ou N) e o estado seguinte, por exemplo A 0 -> 1 R B. A seta e as vírgulas são opcionais. Use _ para uma célula vazia e # para um comentário. A máquina começa no estado da primeira regra; um estado seguinte chamado H ou halt fá-la parar, e accept e reject fazem-na parar com um veredicto.
Uma máquina de Turing consegue mesmo calcular tudo?
Tudo o que qualquer computador consiga calcular, com fita e tempo suficientes: é a tese de Church-Turing. Uma máquina de Turing não tem limite de memória, por isso, nesse sentido, é mais poderosa do que qualquer computador real, embora muito mais lenta. O que não consegue fazer é responder a todas as perguntas: Turing provou que nenhuma máquina pode decidir, para todos os programas e entradas, se vão parar.
Porque é que o contador nunca para?
As suas regras nunca levam a um estado de paragem. Continua a somar 1 a um número binário na extremidade direita da fita e a voltar para trás, por isso o número cresce para sempre. O problema da paragem de Turing diz que nenhum método geral consegue dizer, para todas as máquinas, se vão parar; neste contador simples vê-se, mas para algumas máquinas com apenas seis estados ninguém sabe ainda.
Como é que o castor atarefado de cinco estados consegue dar aqui 47 milhões de passos?
A fita é guardada como um array compacto que cresce nos dois sentidos, e na definição Muito rápida a aplicação executa centenas de milhares de passos entre atualizações do ecrã, por isso a execução completa demora poucos segundos num navegador moderno. O diagrama regista apenas os primeiros 400 passos, porque uma imagem de 47 milhões de linhas não caberia em nenhum ecrã.
É enviado algo para um servidor?
Não. O programa é executado no seu navegador, e o seu programa e a sua entrada ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor