Dein letzter Login ist schon eine Weile her.

Bitte überprüfe, ob alle Angaben in Deinem Profil noch aktuell sind.


27.04.2020
von Jesko
in IT-Talents

Was ist eine Turingmaschine?

x
Für Unternehmen:
IT-Nachwuchs kennenlernen!
Jetzt starten

Von der Turingmaschine zum Quantencomputer

Die Turingmaschine ist ein klassisches Konzept, das noch vor der Computer-Ära entstanden ist. Dabei handelte es sich um ein logisches Rechenkonstrukt und nicht um eine echten Computer. Das Modell beschreibt, wie ein Rechner eine formalisierte Aufgabe löst, um zum Ergebnis zu gelangen, und welche Anforderungen an den Algorithmus gestellt werden, damit die Maschine die Aufgabe versteht und korrekt ausführt.

Lesezeit: ca. 5 Min.

Bewerten

Themen auf dieser Seite:

Der britische Mathematiker Alan Turing hat 1936 ein abstraktes universelles Modell vorgeschlagen, um das Konzept eines Algorithmus anschaulich zu machen und die Möglichkeiten von Algorithmen mit Hilfe dieses Modells theoretisch zu erforschen. Dabei handelte es sich um ein logisches Rechenkonstrukt und nicht um eine echte physikalische Rechenmaschine. Obwohl es damals noch keine Computer gab, beschreibt das Modell, wie ein Rechner eine formalisierte Aufgabe löst, um zum Ergebnis zu gelangen, und welche Anforderungen an den Algorithmus gestellt werden, damit die Maschine die Aufgabe versteht und korrekt ausführt.

Das von Turing erfundene theoretische Modell eines Rechners wurde Turingmaschine genannt. Turing wollte sein Modell dazu verwenden, um entweder die Existenz oder die Unmöglichkeit der Existenz eines Algorithmus für eine bestimmte Aufgabe nachzuweisen. Die klassische Turingmaschine ist ein extrem vereinfachtes Modell, das sich jedoch beliebig erweitern und "aufrüsten" lässt, um komplexere Aufgaben zu formalisieren, zu visualisieren und zu beschreiben. Auch Operationen, die von modernen realen Computern ausgeführt werden oder in Netzwerkprotokollen realisiert sind, kann man in einer Turingmaschine nachbilden.

Die Turingmaschine ist ein klassisches Konzept, das noch vor der Computer-Ära entstanden ist. Du kannst dir eine Turingmaschine am besten vorstellen und dich mit diesem Konzept vertraut machen, indem Du die Begriffe, die Alan Turing ursprünglich bei Beschreibung seiner Maschine verwendet hatte, in gebräuliche Begriffe der modernen Informationstechnik wie beispielsweise externe Daten, Lese- und Schreibzugriffe, Zustände, Befehle und Aktionen übersetzt. Solche modernen Begriffe werden wir hier verwenden, weil sie die Grundbegriffe der Informatik sind und die Arbeitsweise einer Turingmaschine verständlich machen.

IT-Talents.de ist Deine Plattform für Förderung und Weiterbildung während des IT-Studiums!
Fördermöglichkeiten ansehen


Was ist eine Turingmaschine?

Die klassische Turingmaschine besteht aus einem beidseitig in Zellen unterteilten Endlosband (als Datenspeicher mit Lese- und Schreibzugriff für die aktuelle Zelle) und einem Automaten, der nach den vordefinierten Regeln gesteuert wird. Entsprechend den Daten (dem Zeichen) der aktuell gelesenen Zelle und dem aktuellen Zustand führt die Turingmaschine bestimmte Aktionen aus, die in den Regeln definiert sind. Die Regeln sind in Form einer Tabelle spezifiziert und bilden wie in einem echten Computer das eigentliche Programm, nach dem die Turingmaschine arbeitet, wenn sie eine Aufgabe löst. Für alle zulässigen Daten, die als Buchstaben des externen Alphabets vom Band ausgelesen werden können, und für alle möglichen Zustände des Automaten definiert die Tabelle die entsprechenden Aktionen.

Zu möglichen Aktionen gehören der Übergang zum neuen internen Zustand des Automaten, das Überschreiben der Daten in der aktuellen Zelle sowie die Bewegung des Lese-/Schreibkopfes zur nächstliegenden (rechten oder linken) Zelle auf dem Datenband. Die in der der Tabelle definierten Regeln sind die eigentlichen Befehle für die Turing-Maschine bei der Lösung der konkreten Aufgabe. Die Daten auf dem Band und die Regeln in der Tabelle sind voneinander genauso unabhängig wie externe Daten vom Algorithmus. Eine in der Tabelle definierte Regel wird anhand der ausgelesenen Daten und des aktuellen Zustands bestimmt und resultiert eine Aktion. Die Daten auf dem Band sind etwa externe Ereignisse, die die Turingmaschine entsprechend den in der Tabelle festgelegten Regeln bearbeitet, um die passenden Aktionen in der Tabelle zu finden und anzuwenden.

Damit Du eine Turingmaschine zur Lösung einer bestimmten Aufgabe verwenden kannst, musst Du die folgenden Komponenten beschrieben:

  • Externes Alphabet - eine endliche Menge, deren Elemente Buchstaben (Zeichen) genannt werden. Einer der Buchstaben dieses Alphabets muss ein leeres Zeichen beziehungsweise ein Trennzeichen sein.
  • Internes Alphabet - eine endliche Menge von Zuständen des Automaten. Einer der Zustände (q1) muss initial sein, um das Programm zu starten. Ein anderer der Zustände (q0) muss der Zustand der Unterbrechung sein, um die Ausführung des Programms zu beenden.
  • Übergangstabelle - sie beschreibt das Verhalten des Automaten in Abhängigkeit von seinem aktuellen Zustand und dem aktuell gelesenen Zeichen.

Eine Turingmaschine kann das Zeichen der aktuellen Zelle auslesen oder auch überschreiben, den Lese-/Schreibkopf zur nächstliegenden entweder linken oder rechten Zelle des Datenbandes positionieren und den internen Zustand entsprechend den ausgelesenen Daten ändern. Alle möglichen Kombinationen der internen Zustände und der zulässigen externen Daten sind als Regeln in der Tabelle definiert und bestimmen, welches Zeichen in die aktuelle Zelle geschrieben werden soll, in welche Richtung (nach links oder rechts) sich der Kopf bewegen soll und in welchen Zustand der Automat übergeht. Zu möglichen Aktionen gehören auch solche, die den Kopf nicht zur nächsten Zelle bewegen, die Daten der aktuellen Zelle nicht überschreiben oder den aktuellen Zustand nicht ändern.

Auf IT-Talents.de kannst Du Dich mit dem Who-is-Who der IT-Branche vernetzen!
Jetzt Top-Unternehmen anschauen


Beispiel einer Turingmaschine

Angenommen, auf dem Band befindet sich ein Wort, das aus den Zeichen A, B, 1 und 0 besteht, zum Beispiel, 1A0B10. Die Aufgabe ist es, alle Zeichen A und B durch Nullen zu ersetzen. Zum Zeitpunkt des Starts befindet sich der Kopf links über dem ersten Buchstaben des Wortes. Das Programm endet, wenn sich der Kopf über dem leeren Zeichen (einem Trennzeichen) nach dem letzten Buchstaben des Wortes befindet.

Die Regeln in der Tabelle werden wie folgt definiert:

  • Wenn das aktuelle Zeichen 0 ist, dann den Kopf nach rechts bewegen (0/->).
  • Wenn das aktuelle Zeichen 1 ist, dann den Kopf nach rechts bewegen (1/->).
  • Wenn das aktuelle Zeichen A ist, dann das Zeichen in 0 ändern und den Kopf nach rechts bewegen (A/0,->).
  • Wenn das aktuelle Zeichen B ist, dann das Zeichen in 0 ändern und den Kopf nach rechts bewegen (B/0,->).

Schrittweise Ausführung des Programms bei Bearbeitung der Buchstaben nacheinander, von links nach rechts:

  1. Zeichen (1): 1A0B10 -> 1A0B10
  2. Zeichen (A): 1A0B10 -> 100B10
  3. Zeichen (0): 100B10 -> 100B10
  4. Zeichen (B): 100B10 -> 100010
  5. Zeichen (1): 100010 -> 100010
  6. Zeichen (0): 100010 -> 100010
  7. Zeichen (Trennzeichen): Ende

Das resultierende Wort am Ende der Programmausführung ist 100010.

Eine weitere sehr anschauliche Erklärung (auf Englisch) zur Turingmaschine findest Du hier:

Fazit

Die Turingmaschine ist eine der faszinierendsten und aufregendsten intellektuellen Entdeckungen des 20. Jahrhunderts. Dies ist ein einfaches und nützliches abstraktes Computermodell, das häufig ausreichend ist, um jede Computeraufgabe zu formalisieren und den gefundenen Algorithmus in einer Programmiersprache zu implementieren. Dank einem einfachen jedoch universellen und erweiterbaren Konzept bildet die Turingmaschine die Grundlage der theoretischen Informatik. Das Konzept führt zu einem tieferen Verständnis sowohl von digitalen Computern als auch von Netzwerkprotokollen und digitaler Kommunikation.

Mit Hilfe der Turingmaschine wurden komplexe wissenschaftliche Rechenprobleme identifiziert, die mit gängigen Computern und traditionellen sequenziellen Algorithmen nicht lösbar sind. Es ist jedoch zu erwarten, dass eine Quanten-Turingmaschine zur Beschreibung von Quantenalgorithmen für Quantencomputer erfunden wird, die das Computing der Zukunft revolutioniert und zu bahnbrechenden Entwicklungen und Technologien führt.

Aktuelle Aktionen:

IT Recruiting-Day Light

Master@BWI!

Starte durch und komm zum IT Recruiting-Day Light ins Phantasialand!
Bewirb Dich bis 06. September bequem online und nutze Deine Chance!


Jetzt bewerben!

IT-Talents ist ein Netzwerk nur für IT'ler. Auf unserer Plattform kannst Du Dich als registriertes Mitglied mit wenigen Klicks auf die Jobs unserer Partnerunternehmen oder auf IT-Projekte für Studierende bewerben. Darüberhinaus führen wir Wettbewerbe durch und vergeben IT-Stipendien.

Jetzt Mitglied werden.

Verwandte Artikel

Was ist GAIA-X?

26. Jun 2020 in IT-Talents

Europäische Konzerne wünschen sich eine europäische Cloud. Am 4. Juni wurden ersten Einzelheiten zur technischen St…

weiter

Die 6 besten PHP Frameworks 2020

11. Jun 2020 in IT-Talents

Websites sind im Laufe der Zeit komplexer und anspruchsvoller geworden. Positiv zu vermerken ist, dass sie jetzt…

weiter

Was ist ein binäres System?

08. Jun 2020 in IT-Talents

Im Speicher eines Computers sind Daten und Programmcode als eine Folge von Zahlen 0 und 1 dargestellt. Das ist möglich, …

weiter

Was ist Reinforcement Learning im Machine Learning?

27. May 2020 in IT-Talents

AlphaGo von Google ist ein enorm Leistungsfähiges Programm - zumindest in seinem eingeschränkten Nutzungsbereich. A…

weiter

Machine Learning: Was bedeutet Accuracy und Precision?

19. May 2020 in IT-Talents

Machine Learning ist ein Teilgebiet der künstlichen Intelligenz und befasst sich mit der Verbesserung von …

weiter

Was macht ein Softwareentwickler?

06. May 2020 in IT-Talents

Wir klären in diesem Ratgeber die Fragen, welche Aufgaben ein Softwareentwickler zu erfüllen hat, welche V…

weiter

Was ist Supervised und Unsupervised Learning?

04. May 2020 in IT-Talents

Vielleicht hast du auch schon mal von den Begriffen Supervised Learning und Unsupervised Learning gehört, welche …

weiter

Was ist Ruby?

02. May 2020 in IT-Talents

Ruby ist ein objektorientierter Programmierspracheninterpreter, der vom Programmierer Japaner Yukihiro "Matz" Matsumoto…

weiter

Schnell-Login für unsere Mitglieder

Tipp: Halte Dein Profil aktuell.

Lass' uns wissen, falls sich etwas Neues bei Dir ergibt.

Tipp: Vervollständige Dein Profil für noch bessere Karrierechancen.

Bist Du Schüler, Student oder bereits berufstätig? Teile uns Deinen aktuellen Status mit, damit wir Dir sinnvolle Aufgaben anbieten können.

Jetzt Status angeben

Wann stehst Du der IT-Branche zur Verfügung?

Bitte Monat und Jahr angeben.

{{ perspectiveForm.availableFrom.$error.dynamic }}

Neuer Versuch

Wo möchtest Du durchstarten?

{{ location.geolocation.name }}×
Bitte mindestens ein Ort angeben.

Als {{currentUser.status.title}} bist Du bereit für:


Lade Beschäftigungsarten

Bitte wähle den Zeitpunkt, Ort und min. eine Beschäftigungsart aus.

You have voted!
Schliessen
Vote for:
stars
Vote
You have not rated!