Java desafio de programação: Criação de uma simples máquina de Turing
Em 1936, o matemático Alan Turing concebeu uma aparentemente simples tipo de máquina computacional chamado de Máquina de Turing. Turing nunca realmente construiu uma máquina de Turing. Em vez disso, era um dispositivo hipotético que ele inventado para auxiliar no estudo de computability - isto é, se os problemas complexos podem ser resolvidos por passos computacionais e se uma máquina pode ser concebido que pode resolver qualquer problema calculável. (Se você estiver interessado em saber mais sobre a história ou a aplicação de máquinas de Turing, você pode encontrar muitos artigos sobre eles na Internet. Basta usar qualquer provedor de busca para procurar por "máquina de Turing".)
A operação de uma máquina de Turing é simples. Ele encarna apenas alguns conceitos básicos:
O coração de uma máquina de Turing é um infinitamente longo da fita, que está dividido em células nas quais a informação pode ser escrita.
Na prática, é 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.
As informações que podem ser escritos em cada célula está limitado a um único símbolo, tal como um 0 ou um 1. No entanto, a informação pode ser representado pelos valores combinados de células sucessivas.
Por exemplo, você pode representar valores numéricos por ocorrências sucessivas de o símbolo 1 seguido por um 0. Assim, 1110 representam o valor 3, porque há três 1's- 111.111.011.110 pode representar os valores 6 e 4 (seis 1 da seguido por um zero, seguido por quatro 1 da seguido por outro zero).
A Máquina de Turing contém uma leitura e escrita cabeça que está sempre posicionada sobre um (e somente um) de células da fita.
Esta cabeça de leitura-escrita pode ler o símbolo que está contido na célula. Também pode apagar o símbolo e, se desejado, escrever um novo símbolo no seu lugar. A célula sobre a qual a cabeça de leitura e escrita é posicionado é referido como o célula atual ou o celular cabeça.
A fita é motorizado de modo que ele pode ser movido para a esquerda ou para a direita debaixo da cabeça de leitura e escrita de uma célula de cada vez.
A máquina tem um Estado, que é representada por um símbolo, tal como uma letra do alfabeto.
Como qualquer computador, uma máquina de Turing pode ser programado. No entanto, um programa para uma máquina de Turing não se assemelha remotamente um programa Java.
Em vez disso, um programa de máquina de Turing é 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 determinado símbolo e a máquina está em um determinado estado. Por exemplo, uma regra pode ditar o que fazer se a célula atual contém um 1 e o estado da máquina é "a".
Cada regra pode especificar qualquer um dos três ações:
Apagar a célula atual ou escrever um novo valor para a célula.
Mover a fita de uma célula para a esquerda ou uma célula para a direita.
Alterar o estado da máquina para um novo estado.
Por exemplo, uma regra pode especificar que, se a célula atual contém um 1 e o estado da máquina é "a", da Máquina de Turing deve escrever um 0 na célula atual, avançar a fita uma célula para a direita, e alterar o estado da máquina a "b."
Além de um programa, a fita de máquina de Turing pode ter um valor inicial.
Isso é ele- que é toda a definição 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, aceitar as seguintes limitações nesta versão da máquina de Turing:
A fita não tem que ser infinita. Você pode usar qualquer recurso de Java - uma matriz, uma string, ou uma coleção - para representar a fita.
(Note que, embora a fita não tem que ser infinito, você deve ser capaz de mover-se facilmente para a esquerda ou à direita 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 será capaz de mover para a esquerda a partir daí).
Uma célula pode estar vazia ou pode conter qualquer letra ou do numeral. Uma célula vazia é representada por um caractere sublinhado.
O estado pode ser qualquer um único 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 para cada regra, como segue:
célula atual: O valor a ser combinado para a célula atual.
Estado atual: O valor a ser combinado para o estado atual da máquina.
Novo celular: O valor que escrever para a nova célula. _ Para apagar a célula, * para deixar a célula inalterada.
Movimento: G ou R para mover a fita para a esquerda ou para a direita; H para travar a programação qualquer outro personagem para não mover a fita.
Novo estado: O novo valor para o estado da máquina.
Por exemplo, o seguinte diz que quando a célula atual for 1 e o estado é "a", a célula atual deve ser definido como 0, a fita movida uma célula para a esquerda, eo estado deve ser definido como "b"
1 a 0 L b
A primeira linha do arquivo de texto deve conter uma string que representa os valores iniciais para a fita.
A segunda linha do arquivo de texto deve conter o estado inicial.
A figura a seguir mostra a interface do usuário para a solução de amostra, mas você é livre para usar qualquer design de interface de usuário que você gostaria para este projeto.
Aqui estão algumas considerações para a criação da interface:
Valor e célula atual: No mínimo, você deve mostrar o valor da fita e realçar a célula atual.
Ferramentas e visualizaçã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.
A execução do programa: Você pode fornecer uma maneira para que o usuário executar o programa carregado do início ao fim, bem como uma maneira para que o usuário de um único passo através do programa clicando em um botão para executar cada etapa do programa.
Carregar o programa: Você deve fornecer botões que permitem ao usuário carregar um programa máquina de Turing a partir de um arquivo de texto e que permitem que o usuário reiniciar o aparelho para executar o programa novamente.
Aqui vai uma dica para a implementação da fita infinita: Use três variáveis de cadeia para manter os valores de fita, um para o único caractere armazenado na célula atual, um segundo para os caracteres à esquerda da célula atual, e um terceiro para os personagens a direita da célula corrente. Você pode então mover-se facilmente a célula atual para a esquerda ou direita usando a combinação certa de concatenação e operações de substring.
Você pode encontrar a solução para este desafio na guia Downloads do Java All-in-One For Dummies, 4 página do produto Edition.
Boa sorte!