Java Programming Challenge: Criando uma máquina de Turing simples - manequins

Em 1936, o matemático Alan Turing concebeu um tipo de máquina computacional enganosamente simples chamado Turing Machine . Turing nunca criou uma máquina de Turing. Em vez disso, era um dispositivo hipotético que ele inventou para ajudar no estudo da computação - ou seja, se os problemas complexos podem ser resolvidos por etapas computacionais e se uma máquina pode ser concebida que pode resolver qualquer problema computable. (Se você estiver interessado em saber mais sobre o histórico ou a aplicação das máquinas Turing, você pode encontrar muitos artigos sobre eles na Internet. Basta usar qualquer provedor de pesquisa para procurar "Turing machine".)

A operação de uma máquina de Turing é simples. Ele incorpora apenas alguns conceitos básicos:

O coração de uma máquina de Turing é uma fita infinitamente longa que é dividida em células nas quais as informações podem ser escritas.

Na prática real, é claro, nenhum dispositivo físico pode ter um número infinito de células. Mas na teoria de uma máquina de Turing, a fita é infinita.
A informação que pode ser escrita em cada célula é limitada a um único símbolo, como um 0 ou um 1. No entanto, a informação pode ser representada pelos valores combinados de células sucessivas.

Por exemplo, você pode representar valores numéricos por ocorrências sucessivas do símbolo 1 seguido por um 0. Assim, 1110 representam o valor 3 porque existem três 1; 111111011110 pode representar os valores 6 e 4 (seis 1 seguido por um zero, seguido por quatro 1 seguido de outro zero).
A máquina de Turing contém uma cabeça de leitura-gravação que está sempre posicionada sobre uma (e uma única) das células da fita.

Esta cabeça de leitura e gravação pode ler o símbolo que está contido na célula. Também pode apagar o símbolo e, se desejado, escreva um novo símbolo em seu lugar. A célula sobre a qual a cabeça de leitura e gravação está posicionada é referida como célula atual ou célula principal .
A fita é motorizada para que ela possa ser movida para a esquerda ou para a direita sob a cabeça de leitura-escrita uma célula por vez.
A máquina tem um estado , que é representado por um símbolo, como uma letra do alfabeto.

Como qualquer computador, uma máquina de Turing pode ser programada. No entanto, um programa para uma máquina de Turing não se assemelha remotamente a um programa Java.

Em vez disso, um programa Turing Machine é simplesmente um conjunto de regras que são avaliadas para determinar quais ações a máquina deve tomar. Cada regra identifica uma ação a ser tomada quando a célula atual contém um símbolo dado e a máquina está em um determinado estado.Por exemplo, uma regra pode ditar o que fazer se a célula atual contiver 1 e o estado da máquina é "a".

Cada regra pode especificar uma das três ações:

Apague a célula atual ou escreva um novo valor para a célula.
Mova a fita uma célula para a esquerda ou uma célula para a direita.
Mude o estado da máquina para um novo estado.

Por exemplo, uma regra pode especificar que se a célula atual contiver 1 e o estado da máquina for "a", a Máquina de Turing deve escrever um 0 na célula atual, avançar a fita uma célula para a direita e mudar o estado da máquina para "b. "

Além de um programa, a fita da máquina Turing pode ter um valor inicial.

É isso; Essa é a definição completa de uma Máquina de Turing. Apesar de sua simplicidade, uma Máquina de Turing pode calcular qualquer coisa de 2 + 2 para a trajetória de um foguete para Marte.

Para este desafio, você deve criar uma Máquina de Turing muito simples. Para simplificar o problema, aceite as seguintes limitações nesta versão do Turing Machine:

A fita não precisa ser infinita. Você pode usar qualquer recurso Java - uma matriz, uma string ou uma coleção - para representar a fita.

(Note que, embora a fita não precise ser infinita, você deve poder mover-se facilmente para a esquerda ou para a direita a partir da célula atual. Se você optar por usar uma matriz, não comece com a célula atual no elemento 0 porque você não poderá se mover para a esquerda a partir de lá.)
Uma célula pode estar vazia ou pode conter qualquer letra ou numeral. Uma célula vazia é representada por um caractere de sublinhado.
O estado pode ser qualquer caractere alfanumérico.
O programa para a máquina de Turing será lido a partir de um arquivo de texto. Este arquivo de texto contém uma regra por linha. Cada regra contém cinco caracteres, separados por espaços, que fornecem os detalhes de cada regra, da seguinte forma:
- Célula atual: O valor a ser correspondido para a célula atual.
- Estado atual: O valor a ser combinado para o estado atual da máquina.
- Nova célula: O valor a ser gravado na nova célula. _ para apagar a célula, * para deixar a célula inalterada.
- Movimento: L ou R para mover a fita para a esquerda ou para a direita; H para interromper o programa; qualquer outro personagem para não mover a fita.
- Estado novo: O novo valor para o estado da máquina.
Por exemplo, o seguinte diz que, quando a célula atual é 1 e o estado é "a", a célula atual deve ser definida como 0, a fita moveu uma célula para a esquerda e o estado deve ser definido como " b: "
```
1 a 0 L b
```
- A primeira linha do arquivo de texto deve conter uma seqüência de caracteres que represente os valores iniciais para a fita.
- A segunda linha do arquivo de texto deve conter o status inicial.

A figura a seguir mostra a interface do usuário para a solução de amostra, mas você pode usar qualquer projeto de interface de usuário que você gostaria para este projeto.

Uma interface Turing Machine potencial.

Aqui estão algumas considerações para criar a interface:

Valor e célula atual: No mínimo, você deve mostrar o valor da fita e destacar a célula atual.
Ferramentas e exibição: Você também deve fornecer a capacidade de iniciar, parar ou reiniciar a execução do programa, e você deve exibir os resultados de cada etapa do programa.
Execução do programa: Você pode fornecer uma maneira para o usuário executar o programa carregado do início ao fim, bem como uma maneira para o usuário entrar em um único passo através do programa clicando em um botão para executar cada etapa do programa.
Carregando o programa : Você deve fornecer botões que permitem que o usuário carregue um programa Turing Machine a partir de um arquivo de texto e que permita ao usuário redefinir a máquina para executar o programa novamente.

Aqui está uma dica para implementar a fita infinita: use três variáveis de string para manter os valores da fita, um para o caractere único armazenado na célula atual, um segundo para os caracteres à esquerda da célula atual e um terceiro para os caracteres à direita da célula atual. Você pode mover facilmente a célula atual para a esquerda ou para a direita usando a combinação certa de operações de concatenação e substring.

Você pode encontrar a solução para este desafio na guia Downloads da página de produtos Java All-in-One For Dummies, 4th Edition.

Boa sorte!