Java Programming Challenge: Erstellen einer einfachen Turing-Maschine - Dummies

Im Jahr 1936 erfand der Mathematiker Alan Turing eine täuschend einfache Art von Rechenmaschine, genannt Turing Machine . Turing hat nie eine Turingmaschine gebaut. Stattdessen war es ein hypothetisches Gerät, das er zusammengestellt hatte, um beim Studium der Berechenbarkeit zu helfen - das heißt, ob komplexe Probleme durch Rechenschritte gelöst werden können und ob eine Maschine entwickelt werden kann, die jedes berechenbare Problem lösen kann. (Wenn Sie mehr über die Geschichte oder Anwendung von Turing-Maschinen erfahren möchten, finden Sie viele Artikel über sie im Internet. Verwenden Sie einfach einen beliebigen Suchanbieter, um nach "Turing machine" zu suchen.)

Der Betrieb einer Turingmaschine ist einfach. Es enthält nur ein paar grundlegende Konzepte:

1. Das Herz einer Turing-Maschine ist ein unendlich langes Band, das in Zellen unterteilt ist, auf die Informationen geschrieben werden können.

   In der tatsächlichen Praxis kann natürlich kein physikalisches Gerät eine unendliche Anzahl von Zellen haben. Aber in der Theorie einer Turing-Maschine ist das Band unendlich.

2. Die Information, die auf jede Zelle geschrieben werden kann, ist auf ein einzelnes Symbol beschränkt, wie z. B. eine 0 oder eine 1. Die Information kann jedoch durch die kombinierten Werte von aufeinander folgenden Zellen dargestellt werden.

   Zum Beispiel könnten Sie numerische Werte durch aufeinanderfolgendes Vorkommen des Symbols 1, gefolgt von einer 0, repräsentieren. Somit repräsentieren 1110 den Wert 3, da es drei Einsen gibt; 111111011110 könnte die Werte 6 und 4 darstellen (sechs Einsen, gefolgt von einer Null, gefolgt von vier Einsen, gefolgt von einer weiteren Null).

3. Die Turing-Maschine enthält einen Lese-Schreib-Kopf , der immer über einer (und nur einer) der Zellen des Bandes positioniert ist.

   Dieser Schreib-Lese-Kopf kann das Symbol lesen, das in der Zelle enthalten ist. Es kann auch das Symbol löschen und, falls gewünscht, ein neues Symbol an seine Stelle schreiben. Die Zelle, über der der Lese-Schreibkopf positioniert ist, wird als die aktuelle Zelle oder die Kopfzelle bezeichnet.

4. Das Band ist motorisiert, so dass es jeweils um eine Zelle nach links oder rechts unter den Schreib-Lese-Kopf bewegt werden kann.

5. Die Maschine hat einen -Zustand , der durch ein Symbol wie einen Buchstaben des Alphabets dargestellt wird.

Wie bei jedem Computer kann auch eine Turing-Maschine programmiert werden. Ein Programm für eine Turing-Maschine ähnelt jedoch nicht im entferntesten einem Java-Programm.

Stattdessen ist ein Turing-Maschinen-Programm einfach ein Satz von Regeln, die ausgewertet werden, um zu bestimmen, welche Aktionen die Maschine ausführen soll. Jede Regel identifiziert eine Aktion, die ausgeführt werden soll, wenn die aktuelle Zelle ein bestimmtes Symbol enthält und sich die Maschine in einem bestimmten Zustand befindet.Beispielsweise kann eine Regel bestimmen, was zu tun ist, wenn die aktuelle Zelle eine 1 enthält und der Maschinenzustand "a" ist.

Jede Regel kann eine von drei Aktionen angeben:

• Löscht die aktuelle Zelle oder schreibt einen neuen Wert in die Zelle.

• Bewegen Sie das Band um eine Zelle nach links oder eine Zelle nach rechts.

• Ändern Sie den Status der Maschine in einen neuen Zustand.

Zum Beispiel könnte eine Regel festlegen, dass, wenn die aktuelle Zelle eine 1 enthält und der Maschinenzustand "a" ist, die Turing-Maschine eine 0 in die aktuelle Zelle schreiben, das Band um eine Zelle nach rechts verschieben und ändern soll. der Maschinenzustand auf "b. "

Zusätzlich zu einem Programm kann das Band der Turing-Maschine einen Anfangswert haben.

Das ist es; das ist die gesamte Definition einer Turingmaschine. Trotz ihrer Einfachheit kann eine Turing-Maschine alles von 2 + 2 bis zur Flugbahn einer Rakete zum Mars berechnen.

Für diese Herausforderung müssen Sie eine sehr einfache Turing-Maschine erstellen. Um das Problem zu vereinfachen, akzeptieren Sie die folgenden Einschränkungen für diese Version der Turing-Maschine:

• Das Band muss nicht unendlich sein. Sie können jedes Java-Feature verwenden - ein Array, eine Zeichenfolge oder eine Sammlung -, um das Band darzustellen.

  (Beachten Sie, dass das Band zwar nicht unendlich sein muss, Sie sich aber leicht von der aktuellen Zelle nach links oder rechts bewegen müssen. Wenn Sie ein Array verwenden, beginnen Sie nicht mit der aktuellen Zelle am Element. 0, weil Sie sich von dort aus nicht mehr nach links bewegen können.

• Eine Zelle kann leer sein oder einen beliebigen Buchstaben oder eine Zahl enthalten. Eine leere Zelle wird durch einen Unterstrich dargestellt.

• Der Status kann ein einzelnes alphanumerisches Zeichen sein.

• Das Programm für die Turingmaschine wird aus einer Textdatei gelesen. Diese Textdatei enthält eine Regel pro Zeile. Jede Regel enthält fünf durch Leerzeichen getrennte Zeichen, die die Details für jede Regel wie folgt angeben:

  • Aktuelle Zelle: Der Wert, der für die aktuelle Zelle abgeglichen werden soll.

  • Aktueller Status: Der Wert, der für den aktuellen Maschinenzustand angepasst werden soll.

  • Neue Zelle: Der Wert, der in die neue Zelle geschrieben werden soll. _ um die Zelle zu löschen, * um die Zelle unverändert zu lassen.

  • Bewegung: L oder R, um das Band nach links oder rechts zu bewegen; H um das Programm anzuhalten; ein anderes Zeichen, um das Band nicht zu bewegen.

  • Neuer Status: Der neue Wert für den Maschinenzustand.

• Zum Beispiel sagt das Folgende, dass, wenn die aktuelle Zelle 1 ist und der Status "a" ist, die aktuelle Zelle auf 0 gesetzt werden sollte, das Band um eine Zelle nach links verschoben wird und der Status auf " b: "

  1 a 0 L b
  

  • Die erste Zeile der Textdatei sollte eine Zeichenfolge enthalten, die die Anfangswerte für das Band darstellt.

  • Die zweite Zeile der Textdatei sollte den Anfangsstatus enthalten.

Die folgende Abbildung zeigt die Benutzeroberfläche für die Beispiellösung. Es steht Ihnen jedoch frei, ein beliebiges Benutzeroberflächendesign für dieses Projekt zu verwenden.

Eine potenzielle Turing Machine-Schnittstelle.

Hier einige Überlegungen zum Erstellen der Schnittstelle:

• Wert und aktuelle Zelle: Mindestens sollten Sie den Wert des Bandes anzeigen und die aktuelle Zelle markieren.

• Tools und Anzeige: Sie sollten auch die Möglichkeit haben, die Ausführung des Programms zu starten, anzuhalten oder neu zu starten. Außerdem sollten Sie die Ergebnisse der einzelnen Schritte des Programms anzeigen.

• Programmausführung: Sie können dem Benutzer die Möglichkeit geben, das geladene Programm von Anfang bis Ende auszuführen, und dem Benutzer die Möglichkeit zu geben, das Programm durch Klicken auf eine Schaltfläche schrittweise auszuführen, um jeden Schritt auszuführen. des Programms.

• Laden des Programms : Sie sollten Schaltflächen bereitstellen, mit denen der Benutzer ein Turing Machine-Programm aus einer Textdatei laden kann und der Benutzer die Maschine zurücksetzen kann, um das Programm erneut auszuführen.

Hier ein Tipp zum Implementieren des unendlichen Bandes: Verwenden Sie drei Stringvariablen, um die Bandwerte zu halten, einen für das in der aktuellen Zelle gespeicherte einzelne Zeichen, einen zweiten für die Zeichen links von der aktuellen Zelle und einen dritten für die Zeichen rechts von der aktuellen Zelle. Sie können die aktuelle Zelle dann einfach nach links oder rechts verschieben, indem Sie die richtige Kombination aus Verkettung und Substring-Operationen verwenden.

Die Lösung für diese Herausforderung finden Sie auf der Registerkarte Downloads der Produktseite Java All-in-One für Dummies, 4th Edition.

Viel Glück!