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

Lesezeit: ca. 5 Min.

Bewerten

Themen auf dieser Seite:

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.

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.

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.

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-Stipendium April 2021 - NRW

1200€ Förderung für IT-Talente aus NRW!


Sei dabei und sichere Dir beim IT-Stipendium NRW bis zu 1200€ Förderung.
Jetzt bewerben!

IT-Stipendium April 2021

Stipendium für Informatiker aus dem gesamten Bundesgebiet


Sei dabei und sichere Dir eines von 3 IT-Stipendien im April 2021.
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 ein Framework? - Definition & Erklärung

20. Nov 2020 in IT-Talents

In Softwareprojekten ist es erforderlich, nicht nur die funktionalen Anforderungen umzusetzen, sondern auch ein…

weiter

Die 5 besten GUI-Clients für Git 2021

05. Nov 2020 in IT-Talents

Git ist ein bekanntes Werkzeug für das Versionsmanagement von Dateien. Entwickelt wurde es für die heute verbreitete H…

weiter

Wozu dient ein Proxy Server?

26. Oct 2020 in IT-Talents

Eine Verbindung zum Internet ist für viele selbstverständlich, aber eine Filterung des Datenverkehrs kann aus den v…

weiter

Was ist PHP und wie kann ich es lernen?

22. Oct 2020 in IT-Talents

Heute erwarten Nutzer ein dynamisches Verhalten Deiner Webseite und genau dafür ist PHP geeignet. Als …

weiter

Was ist Paravirtualisierung? - Virtualisierungstechnologien

06. Oct 2020 in IT-Talents

Der Begriff Virtualisierung bezieht sich auf die Erstellung einer virtuellen statt einer tatsächlichen physischen …

weiter

Was ist Betriebssystemvirtualisierung bzw.…

02. Oct 2020 in IT-Talents

Der Begriff Virtualisierung wird häufig bei Beschreibung und Implementierung abstrakter Hardware- oder Software-Modelle …

weiter

Was ist Virtualisierung? - Virtualisierungstechnologien im…

30. Sep 2020 in IT-Talents

Virtualisierung verspricht effizienten Ressourceneinsatz, einen schnellen Wechsel zwischen verschiedenen…

weiter

Was macht ein Kaufmann im E-Commerce 2020?

03. Jul 2020 in IT-Talents

Der Onlinehandel boomt und macht derzeit einen Großteil der Wirtschaft aus. Mit dem Ausbildungsberuf Kaufmann/frau im …

weiter

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

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!