Défi de programmation java: créer une machine simple de Turing - des nuls

En 1936, le mathématicien Alan Turing un type de machine de calcul faussement simple appelé Machine de Turing . Turing n'a jamais réellement construit une machine de Turing. Au lieu de cela, il a concocté un dispositif hypothétique pour faciliter l'étude de la calculabilité - c'est-à-dire, si des problèmes complexes peuvent être résolus par des étapes de calcul et si une machine peut résoudre n'importe quel problème calculable. (Si vous souhaitez en savoir plus sur l'histoire ou l'application des machines de Turing, vous pouvez trouver de nombreux articles à leur sujet sur Internet, utilisez simplement un moteur de recherche pour chercher "Turing machine".)

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

1. Le cœur d'une machine de Turing est une bande infiniment longue qui est divisée en cellules sur lesquelles l'information peut être écrite.

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

2. Les informations qui peuvent être écrites sur chaque cellule sont limitées à un seul symbole, tel que 0 ou 1. Cependant, les informations peuvent être représentées par les valeurs combinées des cellules successives.

   Par exemple, vous pourriez représenter des valeurs numériques par des occurrences successives du symbole 1 suivi d'un 0. Ainsi, 1110 représente la valeur 3 parce qu'il y a trois 1; 111111011110 peut représenter les valeurs 6 et 4 (six 1 suivis d'un zéro, suivis de quatre 1 suivis d'un autre zéro).

3. La machine de Turing contient une tête de lecture-écriture qui est toujours positionnée sur une (et une seule) des cellules de la bande.

   Cette tête de lecture-écriture peut lire le symbole contenu dans la cellule. Il peut également effacer le symbole et, si vous le souhaitez, écrire un nouveau symbole à sa place. La cellule sur laquelle la tête de lecture-écriture est positionnée est appelée cellule actuelle ou cellule .

4. La bande est motorisée pour pouvoir être déplacée vers la gauche ou la droite sous la tête de lecture-écriture, une cellule à la fois.

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

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

Au lieu de cela, un programme Turing Machine est simplement un ensemble de règles qui sont évaluées pour déterminer les actions que la machine doit effectuer. Chaque règle identifie une action à effectuer lorsque la cellule actuelle contient un symbole donné et que la machine est dans un état donné.Par exemple, une règle peut indiquer ce qu'il faut faire si la cellule actuelle contient un 1 et que l'état de la machine est "a".

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

• Effacer la cellule actuelle ou écrire une nouvelle valeur dans la cellule.

• Déplacez la bande d'une cellule vers la gauche ou d'une cellule vers la droite.

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

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

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

C'est tout. C'est la définition complète d'une machine de Turing. Malgré sa simplicité, une machine de Turing peut calculer n'importe quoi de 2 + 2 à la trajectoire d'une fusée vers Mars.

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

• La bande n'a pas besoin d'être infinie. Vous pouvez utiliser n'importe quelle fonction Java (un tableau, une chaîne ou une collection) pour représenter la bande.

  (Notez que bien que la bande ne doive pas être infinie, vous devez pouvoir vous déplacer facilement à gauche ou à droite de la cellule actuelle.) Si vous choisissez d'utiliser un tableau, ne commencez pas par la cellule courante à l'élément. 0 parce que vous ne pourrez pas vous déplacer à partir de là.)

• Une cellule peut être vide ou contenir n'importe quelle lettre ou n'importe quel chiffre. Une cellule vide est représentée par un caractère de soulignement.

• L'état peut être un 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 de chaque règle, comme suit:

  • Cellule actuelle: Valeur à rechercher pour la cellule actuelle.

  • Etat actuel: Valeur à associer à l'état actuel de la machine.

  • Nouvelle cellule: Valeur à écrire dans la nouvelle cellule. _ pour effacer la cellule, * pour laisser la cellule inchangée.

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

  • Nouvel état: Nouvelle valeur pour l'état de la machine.

• Par exemple, ce qui suit indique que lorsque la cellule courante est 1 et que l'état est "a", la cellule courante doit être définie sur 0, la bande déplacée d'une cellule vers la gauche et l'état sur " b: "

  1 a 0 L b
  

  • La première ligne du fichier texte doit contenir une chaîne représentant les valeurs initiales de la bande.

  • La deuxième ligne du fichier texte doit contenir le statut initial.

La figure suivante montre l'interface utilisateur de l'exemple de solution, mais vous pouvez utiliser n'importe quelle conception d'interface utilisateur pour ce projet.

Une interface potentielle de Turing Machine.

Voici quelques considérations pour créer l'interface:

• Cellule de valeur et de courant: Au minimum, vous devriez montrer la valeur de la bande et mettre en surbrillance la cellule actuelle.

• Outils et affichage: Vous devez également pouvoir démarrer, arrêter ou redémarrer l'exécution du programme et afficher les résultats de chaque étape du programme.

• Exécution du programme: Vous pouvez fournir à l'utilisateur un moyen d'exécuter le programme chargé du début à la fin, ainsi qu'un moyen pour l'utilisateur de parcourir le programme en cliquant sur un bouton pour exécuter chaque étape. du programme.

• Chargement du programme : Vous devez fournir des boutons permettant à l'utilisateur de charger un programme Turing Machine à partir d'un fichier texte et de laisser l'utilisateur réinitialiser la machine pour exécuter à nouveau le programme.

Voici une astuce pour implémenter la bande infinie: Utilisez trois variables de chaîne pour contenir les valeurs de bande, une pour le caractère unique stocké dans la cellule courante, une seconde pour les caractères à gauche de la cellule courante, et une troisième pour les caractères à droite de la cellule actuelle. Vous pouvez ensuite déplacer facilement la cellule actuelle vers la gauche ou vers la droite en utilisant la bonne combinaison d'opérations de concaténation et de sous-chaîne.

Vous pouvez trouver la solution à ce problème dans l'onglet Téléchargements de la page du produit Java Tout-en-un pour les nuls, 4e édition.

Bonne chance!