Was ist turingmaschine?

Turingmaschine

Eine Turingmaschine ist ein theoretisches Modell eines Rechengeräts, das als Grundlage für das Verständnis der Grenzen und Möglichkeiten von Computern dient. Sie wurde 1936 von Alan Turing entwickelt.

Grundlegende Konzepte:

• <a href="https://de.wikiwhat.page/kavramlar/Zustände">Zustände</a>: Die Turingmaschine befindet sich in einem bestimmten Zustand, der ihre aktuelle "Konfiguration" darstellt. Es gibt einen Startzustand und einen oder mehrere Endzustände (Akzeptanzzustände).
• <a href="https://de.wikiwhat.page/kavramlar/Band">Band</a>: Ein unendlich langes Band, das in Zellen unterteilt ist. Jede Zelle kann ein Symbol aus einem endlichen Alphabet speichern.
• <a href="https://de.wikiwhat.page/kavramlar/Kopf">Kopf</a>: Ein Lese-/Schreibkopf, der sich entlang des Bandes bewegen und den Inhalt der aktuellen Zelle lesen oder schreiben kann.
• <a href="https://de.wikiwhat.page/kavramlar/Übergangsfunktion">Übergangsfunktion</a>: Eine Funktion, die basierend auf dem aktuellen Zustand der Maschine und dem Symbol, das der Kopf gerade liest, Folgendes bestimmt:
  • Das Symbol, das auf die aktuelle Zelle geschrieben wird.
  • Die Richtung, in die sich der Kopf bewegt (links oder rechts).
  • Der neue Zustand der Maschine.

Funktionsweise:

Die Turingmaschine beginnt in ihrem Startzustand mit dem Kopf über der ersten Zelle des Eingabebandes. Sie liest das Symbol unter dem Kopf und wendet die Übergangsfunktion an. Die Übergangsfunktion bestimmt die nächste Aktion: ein Symbol wird geschrieben, der Kopf bewegt sich, und die Maschine wechselt in einen neuen Zustand. Dieser Prozess wird fortgesetzt, bis die Maschine entweder in einen Akzeptanzzustand gelangt (was bedeutet, dass die Eingabe akzeptiert wurde) oder in einen Zustand, in dem keine Übergangsfunktion definiert ist (was bedeutet, dass die Eingabe abgelehnt wurde oder die Maschine endlos weiterläuft).

Bedeutung:

• Theoretische Grundlage der Berechenbarkeit: Die Turingmaschine ist ein universelles Rechenmodell. Das heißt, jede Berechnung, die von einem Algorithmus durchgeführt werden kann, kann prinzipiell auch von einer Turingmaschine durchgeführt werden.
• Grenzen der Berechenbarkeit: Sie hilft, die Grenzen dessen zu definieren, was überhaupt berechenbar ist. Das Halteproblem ist ein bekanntes Beispiel für ein Problem, das von keiner Turingmaschine gelöst werden kann.
• Grundlage für moderne Computer: Obwohl moderne Computer völlig anders aufgebaut sind, basieren sie auf den gleichen grundlegenden Prinzipien wie die Turingmaschine.

Formale Definition:

Eine Turingmaschine wird formal definiert als ein 7-Tupel:

M = (Q, Σ, Γ, δ, q0, B, F)

wobei:

• Q eine endliche Menge von Zuständen ist.
• Σ eine endliche Menge von Eingabesymbolen ist (das Eingabealphabet).
• Γ eine endliche Menge von Bandsymbolen ist (das Bandalphabet), wobei Σ ⊆ Γ.
• δ: Q × Γ → Q × Γ × {L, R} die Übergangsfunktion ist (wobei L für "links" und R für "rechts" steht).
• q0 ∈ Q der Startzustand ist.
• B ∈ Γ \ Σ das Blank-Symbol ist.
• F ⊆ Q die Menge der akzeptierenden Zustände ist.