Java desafio de programação: a criação de uma máquina de turing simples
Em 1936, o matemático Alan Turing concebeu uma enganosamente simples tipo de máquina computacional chamado de Máquina de Turing
Conteúdo
Video: [BlueScope #2] Desafios em aprender programação
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 fita que é dividida em células para que as informações podem ser escritas.
Na prática real, é claro, não há 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 escrito em cada célula está limitada 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, pode representar valores numéricos por ocorrências sucessivas do símbolo 1 seguido por um 0. Assim, 1110 representa o valor 3 porque há três 1`s- 111111011110 pode representar os valores 6 e 4 (seis 1 de seguida por um zero, seguido por quatro de 1 seguido por outro zero).
A Máquina de Turing contém uma ler-escrever cabeça que está sempre posicionada sobre um (e só 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 em seu lugar. A célula durante o qual a cabeça de leitura e gravação está posicionada é referido como o célula atual ou o celular cabeça.
A fita é motorizada para que ele possa ser movido para a esquerda ou para a direita sob a leitura e escrita cabeça uma célula de cada 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 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 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 é “um”, a Máquina de Turing deve escrever um 0 na célula actual, 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 de máquina de Turing pode ter um valor inicial.
Video: D3SAFI66 #010 - Cálculo simples (programação C)
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:
Video: Lógica de Programação
A fita não tem que ser infinita. Você pode usar qualquer recurso Java - um array, uma corda, 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 de lá.)
Uma célula pode estar vazia ou pode conter qualquer letra ou número. 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 o celular, * a deixar a célula inalterada.
Movimento: L ou R para mover a fita para a esquerda ou direita; H para deter o programa- 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 é 1 eo estado é “a”, a célula atual deve ser definido como 0, a fita moveu uma célula para a esquerda, eo estado deve ser definido como “b”
1-A 0 G b
A primeira linha do arquivo de texto deve conter uma cadeia que representa 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 da amostra, mas você é livre para usar qualquer design de interface de usuário que você gostaria para este projeto.
Video: MAC0327 - Desafios de Programação
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 passo do programa.
Carregar o programa: Você deve fornecer botões que permitem ao usuário carregar um programa Máquina de Turing 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 à direita da célula atual. 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!