Défi de programmation Java: la création d'une machine de Turing simples

En 1936, le mathématicien Alan Turing conçu d'une simplicité trompeuse type de machine de calcul appelé Machine de Turing. Turing jamais construit en fait une machine de Turing. Au lieu de cela, il était un dispositif hypothétique qu'il a concocté pour aider à l'étude de la calculabilité - qui est, si les problèmes complexes peuvent être résolus par étapes de calcul et si une machine peut être conçu qui peuvent résoudre tout problème calculable. (Si vous êtes intéressé à en savoir plus sur l'histoire ou l'application de machines de Turing, vous pouvez trouver de nombreux articles sur les sur Internet. Il suffit d'utiliser un fournisseur de recherche pour rechercher des "machine de Turing".)

Le fonctionnement d'une machine de Turing est simple. Il incarne à quelques concepts de base:

1. Le cœur d'une machine de Turing est un infiniment long ruban qui est divisé en cellules sur laquelle l'information peut être écrite.

   Dans la pratique, bien sûr, aucun dispositif physique peut avoir un nombre infini de cellules. Mais dans la théorie de machine de Turing, la bande est infinie.

2. Les informations que l'on peut écrire sur chaque cellule est limité à un seul symbole, par exemple un 0 ou un 1. Cependant, l'information peut être représentée par des valeurs combinées des cellules successives.

   Par exemple, vous pourriez représenter des valeurs numériques par des événements successifs du symbole 1 suivi d'un 0. Ainsi, 1 110 représentent la valeur 3 car il ya trois 1's- 111111011110 pourrait représenter les valeurs 6 et 4 (six 1 est suivi par un zéro, suivies par une de quatre suivi d'un autre zéro).

3. La Machine de Turing contient une lecture-écriture tête qui est toujours positionné sur l'un (et un seul) des cellules de la bande.

   Cette tête de lecture-écriture peut lire le symbole qui est contenu dans la cellule. Il peut également effacer le symbole et, si désiré, écrire un nouveau symbole à sa place. La cellule sur laquelle la tête de lecture-écriture est positionné est désigné comme le cellule courante ou la cellulaire tête.

4. La bande est motorisée de sorte qu'il peut être déplacé vers la gauche ou à droite sous le tête de lecture-écriture d'une cellule à la fois.

5. La machine a un état, qui est représentée par un symbole comme une lettre de l'alphabet.

Comme tout ordinateur, une machine de Turing peut être programmé. Toutefois, un programme pour une machine de Turing ne ressemble pas à distance un programme Java.

Au lieu de cela, un programme de machine de Turing est tout simplement un ensemble de règles qui sont évalués pour déterminer quelles actions la machine devrait prendre. Chaque règle identifie une action à prendre lorsque la cellule active contient un symbole donné et la machine est dans un état donné. Par exemple, une règle peut dicter ce qu'il faut faire si la cellule active contient un 1 et l'état de la machine est "a".

Chaque règle peut spécifier l'une des trois actions:

• Effacer la cellule courante ou d'écrire une nouvelle valeur à la cellule.

• 
  
  
  
  

  Déplacer la bande d'une cellule vers la gauche ou une cellule à la droite.

• Modifier l'état de la machine à un nouvel état.

Par exemple, une règle peut spécifier que si la cellule active contient un 1 et l'état de la machine est "un," la machine de Turing doit écrire un 0 dans la cellule actuelle, avancer la bande d'une cellule vers la droite, et de modifier l'état de la machine à "b".

En plus d'un programme, la cassette de la machine de Turing peut avoir une valeur initiale.

Voilà it- qui est la totalité de la définition d'une machine de Turing. En dépit de sa simplicité, une machine de Turing peut calculer quoi que ce soit de 2 + 2 à la trajectoire d'une fusée vers Mars.

Pour relever ce défi, vous devez créer une machine de Turing très simple. Pour simplifier le problème, accepter les limites suivantes sur cette version de la machine de Turing:

• La bande ne doit pas être infinie. Vous pouvez utiliser toute fonctionnalité Java - un tableau, une chaîne, ou une collection - pour représenter la bande.

  (Notez que bien que la bande ne doit pas être infinie, vous devez être capable de se déplacer facilement gauche ou à droite de la cellule actuelle. Si vous choisissez d'utiliser un tableau, ne pas commencer par la cellule courant à l'élément 0 parce que vous ne sera pas capable de se déplacer de gauche à partir de là.)

• Une cellule peut être vide ou il peut contenir une lettre ou un chiffre. Une cellule vide est représenté par un caractère de soulignement.

• L'état peut être tout seul caractère alphanumérique.

• Le programme de la machine de Turing sera lu à partir d'un fichier texte. Ce fichier texte contient une règle par ligne. Chaque règle contient cinq caractères, séparés par des espaces, qui fournissent les détails pour chaque règle, comme suit:

• Cellulaire actuel: La valeur à être adaptée pour la cellule actuelle.

• État actuel: La valeur à être adaptée pour l'état actuel de la machine.

• Nouvelle cellule: La Valeur à écrire dans la nouvelle cellule. _ Pour effacer la cellule, * de quitter la cellule inchangé.

• Mouvement: L ou R pour déplacer la bande gauche ou à droite; H pour arrêter la programmation tout autre caractère de ne pas déplacer la bande.

• Nouvel état: La nouvelle valeur de l'état de la machine.

1 a 0 b L

La figure suivante montre l'interface utilisateur pour la solution de l'échantillon, mais vous êtes libre d'utiliser toute la conception de l'interface utilisateur que vous souhaitez pour ce projet.

Voici quelques considérations pour la création de l'interface:

• Valeur et cellule actuelle: Au minimum, vous devriez montrer la valeur de la bande et mettre en évidence la cellule courante.

• Outils et affichage: Vous devez également fournir la possibilité de démarrer, arrêter ou redémarrer l'exécution du programme, et vous devriez voir les résultats de chaque étape du programme.

• L'exécution du programme: Vous pouvez fournir un moyen pour l'utilisateur d'exécuter le programme chargé de bout en bout, ainsi que d'un moyen pour l'utilisateur à une seule étape à travers le programme en cliquant sur un bouton pour exécuter chaque étape du programme.

• Chargement du programme: Vous devez fournir les boutons qui permettent à l'utilisateur de charger un programme de machine de Turing à partir d'un fichier texte et que laisser l'utilisateur réinitialiser l'appareil de fonctionner à nouveau le programme.

Voici une astuce pour mettre en œuvre la bande infinie: Utilisez trois variables de chaîne pour contenir les valeurs de bande, un pour le caractère unique stocké dans la cellule actuelle, une deuxième pour les personnages à la gauche de la cellule courante, et un troisième pour les personnages à le droit de la cellule courante. Vous pouvez alors déplacer facilement la cellule courante gauche ou la droite en utilisant la bonne combinaison de concaténation et les opérations sous-chaîne.

Vous pouvez trouver la solution à ce défi sur le Téléchargements onglet du Java All-in-One For Dummies, 4ème page de produits d'édition.

Bon chance!