Diskussion:Turingmaschine

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Turingmaschine“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Zum Archiv

Wie wird ein Archiv angelegt?

Automatische Archivierung

Auf dieser Seite werden Abschnitte monatlich automatisch archiviert, deren jüngster Beitrag mehr als 365 Tage zurückliegt und die mindestens 2 signierte Beiträge enthalten. Um die Diskussionsseite nicht komplett zu leeren, verbleiben mindestens 5 Abschnitte. Die Archivübersicht befindet sich unter Archiv.

"Halteproblem"

In der obigen Definition ist das Programm fest in die Maschine eingebaut und kann nicht verändert werden. Man kann aber eine universelle Turingmaschine definieren, welche die Kodierung einer Turingmaschine als Teil ihrer Eingabe nimmt, und das Verhalten der kodierten Turingmaschine auf der ebenfalls gegebenen Eingabe simuliert. Aus der Existenz einer solchen universellen Turingmaschine folgt z. B. die Unentscheidbarkeit des Halteproblems. Eine ähnliche Idee, bei der das Programm als ein Teil der veränderbaren Eingabedaten betrachtet wird, liegt auch fast allen heutigen Rechnerarchitekturen zugrunde (Von-Neumann-Architektur). Eigentlich reicht bereits die normale Turing-Maschine und die Möglichkeit der Gödelisierung von Turing-Programmen aus, um das Halteproblem zu beweisen.

Unendlichkeit und das Halteproblem

Geht es nicht schon damit los, daß ein Teil der Turing-Maschine ein unendliches (sic!) Speicherband sei? Gibt es eine mathematische Unschärferelation? Gödel hat ja nur "nein" gesagt.

Eine Turing-Maschine hat soviel Speicherband, wie sie jeweils gerade braucht. Sie kriegt sozusagen auf Anfrage eine weiteres Feld. Das Speicherband ist potentiell, aber nicht aktual unendlich.

Tatsächlich ist es völlig egal, ob das Speicherband aktual oder potentiell unendlich ist. Das mit dem Anfügen eines weiteren Feldes ist nur eine bildiche Vorstellung, um die Funktion einer Turingmaschine einem Nicht-Mathematiker zu vermitteln. In der Tat ist die wahre Turingmaschine aber eine rein mathematische Sache. Und dabei ist das Band einfach eine Abbildung der natürlichen Zahlen (für den einseitigen Fall) oder der ganzen Zahlen (beidseitig unendliches Band) auf das Bandalphabet. Eine solche Abbildung ist ein mathematisches Objekt, eine simple Menge, die selbst unendlich ist (denn es ist ja eine Abbildung einer unendlichen Menge auf eine nichtleere Menge). Das heißt: Sie ist genau wie die Menge der natürlichen Zahlen ->aktual<- unendlich. Kurzum: Das Band ist mathematisch exakt betrachtet aktual unendlich. Und wir müssen hier die mathematische Definition nutzen, denn die Turingmaschine ist nicht das Produkt eines Ingeneurs, sondern eines Mathematikers!

Mögliche Verbesserung (1) "Informelle Beschreibung"

Im Abschnitt "Informelle Beschreibung" wird das "Blank" (Leerzeichen, im weiteren Text meist als Quadrat □ symbolisiert) als "zusätzliches Zeichen" das "zugelassen" ist bezeichnet. Es ist also ein Zeichen aus dem Bandalphabet (und damit auch dem Eingabealphabet). Etwas weiter unten folgt dann der Satz "Die Startposition der Turingmaschine ist am Anfang des Eingabeworts, d. h. an der Position des ersten Eingabezeichens." Das ist missverständlich, da es bedeuten könnte, dass es um das erste Zeichen geht, welches sich auf dem Speicherband befindet. Da das Speicherband jedoch unendlich lang ist und das Blank ebenfalls ein Zeichen ist, gibt es in diesem Sinne kein erstes Eingabezeichen. Gemeint ist natürlich das Eingabezeichen, das sich zum Zeitpunkt des Starts der Programmausführung unter dem Lese-/Schreibkopf befindet, welches also rein zeitlich gesehen als erstes gelesen wird. --Payton (Diskussion) 18:55, 19. Feb. 2019 (CET)

Das ist im Artikel vielleicht tatsächlich nicht wirklich gut ausgedrückt. Nachfolgend meine bescheidene Sicht der Dinge.

Zum "Blank": Das "Blank" ist eben kein Zeichen des definierten Maschinen(Band)alphabets. Es stellt ein erlaubtes, leeres Feld auf dem Band dar, das aber von der Maschine ebenso bearbeitet werden kann wie ein (mit einem Zeichen aus dem Maschinenalphabet) gefülltes Feld (bearbeitet = gelesen und beschrieben). Das Beschreiben/Benennen eines leeren Feldes als „zusätzliches Zeichen“ ist eine Krücke, derer sich aber auch Fachbücher bedienen. Dann muss nämlich nicht von Löschen und Schreiben geredet werden, sondern wenn die Maschine ein Feld löschen soll, so "schreibt" sie ein Blank. Naja, und wenn die Maschine ein leeres Feld genauso behandeln und erzeugen kann, wie gefüllte Felder, dann kann man es halt hilfsweise(!) auch als zusätzliches Zeichen ansehen. Stephen Cole Kleene verwendet das in seinem Buch 'Introduction to Meta-Mathematics' so: Das Maschinenalphabet ist die Liste der Zeichen s₁, s₂, ..., s_j; es enthält also j Zeichen. Dann nimmt er s₀ als leeres Feld hinzu, erwähnt aber, dass das „kein wirkliches Zeichen des Alphabets“ sei.

Zur Startposition/Eingabewort: Wenn man also - so wie ich hierdrüber - folgern kann, dass ein leeres Feld nicht zur Eingabe gehören kann, dann halte ich die Sätze im Artikel „Die Turingmaschine modifiziert die Eingabe auf dem Band nach dem festgelegten Programm. Die Startposition der Turingmaschine ist am Anfang des Eingabeworts, d. h. an der Position des ersten Eingabezeichens.“ sowieso für nicht ganz korrekt. 1.) Eine Maschine muss nicht per se das Eingabewort modifizieren, sondern kann das durchaus auch unverändert stehen lassen; und 2.) kann zumindest theoretisch die Startposition irgendwo auf dem Band liegen (auch inmitten des Eingabewortes). Ob und welchen Sinn genau das wann genau macht oder nicht, sei mal dahingestellt. Die Frage ist also: Wurde irgendwo jemals definiert, dass eine Turingmaschine immer „am Anfang des Eingabeworts“ starten muss? Ich schließe das derzeit aus, denn wo befindet sich denn der Anfang - rechts oder links? Und wer sagt, dass ich überhaupt ein Eingabewort haben muss? Ich kann eine Machine ja auch auf ein jungfräuliches, leeres Band loslassen.

Gruß --Apraphul ^Disk _WP:SNZ 09:45, 20. Feb. 2019 (CET)

Dann gebe ich auch noch meinen Senf dazu:

Zum "Blank": Formal ist das Blanksymbol ist ein spezielles Symbol des Bandalphabets aber nicht teil des Eingabealphabets (diese Begrifflichkeiten gibt es in der Einleitung aber eh noch nicht). Nachdem das Blanksymbol in der mathematischen Formalisierung genau so behandelt wird wie die anderen Bandsymbole wird es aus mathematischer Eleganz auch als Bandsymbol betrachtet (das kann man auch als Krücke sehen).

Zur Startposition/Eingabewort: Jetzt kann man die Startposition theoretisch überall definieren. Es hat sich aber (insbesondere in den Standard-Lehrbüchern) durchgesetzt das erste Zeichen des Eingabeworts (also links) zu nehmen.

Natürlich kann man eine Turing Maschine auch mit leerer Eingabe bzw ohne Eingabe "starten", dann sind die Positionen des Lese-Schreib-Kopf auf dem unendlichen Band nicht unterscheidbar. Ich denke es ist aber sinnvoll sich in der informellen Beschreibung auf den Standard Fall zu konzentrieren und nicht gleich alle formalen Variationen miteinzubeziehen.

Ich würde vorschlagen den jetzigen Text

   Die Turingmaschine modifiziert die Eingabe auf dem Band nach dem festgelegten Programm. Die Startposition der Turingmaschine ist am Anfang des Eingabeworts, d. h. an der Position des ersten Eingabezeichens.

wie folgt zu ändern:

   Eine Berechung für ein Eingabewort startet mit dem Eingabewort auf dem Band und dem Lese- und Schreibkopf auf dem ersten Symbol des Eingabeworts. Die Turingmaschine verarbeitet dann die Eingabe auf dem Band schrittweise nach dem festgelegten Programm.

LG -- Wdvorak (Diskussion) 15:35, 20. Feb. 2019 (CET)

Mögliche Verbesserung (2) "Bedeutung"

Im Abschnitt "Bedeutung" steht der Satz "Das von Hilbert aufgestellte Entscheidungsproblem fragt, ob eine Formel der Prädikatenlogik allgemeingültig ist, also ob jede Interpretation einer mathematischen, d. h. formal logischen Aussage wahr ist." Das scheint mir ungenau formuliert zu sein, denn natürlich ist schon deswegen nicht jede (d.h. jede beliebige, willkürliche, ggf. unsinnige) Interpretation "wahr", weil man ja stets eine bewusst unwahre formulieren kann. Der Satz ist daher unpräzise formuliert. --Payton (Diskussion) 18:59, 19. Feb. 2019 (CET)

Ich verstehe deinen Einwand leider nicht vollständig. Es gibt natürlich Formeln, z.B. $P(a)\vee \neg P(a)$, die für jede mögliche Interpretation wahr sind.

Um den Text klarer zu machen würde ich vorschlagen den Text auf folgendes zu ändern

      Das von Hilbert aufgestellte Entscheidungsproblem fragt, ob eine gegebene Formel der Prädikatenlogik allgemeingültig ist, also ob die Formel unter jeder Interpretation wahr ist.

LG -- Wdvorak (Diskussion) 15:40, 20. Feb. 2019 (CET)

Mögliche Verbesserung (3) "Konfigurationen"

Im Abschnitt "Konfigurationen" wird in der Grafik das leere Element ("kein Wert") im Artikeltext als Quadrat □ symbolisiert, auf dem Band dann aber als "0" dargestellt. Das ist nicht nur inkonsistent, sondern auch grob irreführend (m.E. wäre sogar die Bezeichnung "falsch" zu rechtfertigen). Zwar befindet sich darunter der Kommentar "□ wird hier durch 0 dargestellt", das ist m.E. aber dennoch inakzeptabel da sinnlos und ungerechtfertigt. Man würde auch nicht schreiben "17 wird hier durch 18 dargestellt", ohne dass jeder Leser denken würde: "Was soll der Unsinn?" Inakzeptabel und ärgerlich auch deshalb, weil ja viele, selbst Studenten der Informatik, □ und "0" fälschlich gleichsetzen, auch weil das englische Wort "null" (d.i. "leer", "nichts") formgleich zum deutschen Wort "null" (d.i. "0", englisch "zero") ist. Da es ausgereicht hätte, die Felder, in denen nichts steht, einfach leer zu lassen, gibt es auch nicht den geringsten Grund, etwas hinein zu schreiben, und wenn man den (m.E. unsinnigen) Entschluss fasst, statt nichts doch etwas hineinzuschreiben, ist es aus besagten Gründen die schlechteste aller schlechten Lösungen, ausgerechnet "0" hineinzuschreiben. Denn das leistet dem häufigen Missverständnis Vorschub, die Zahl 0 und der Wert □ seien das Gleiche. Die Zahl 0 steht aber nicht für "kein Wert" (oder "leer" oder "nichts", englisch "null"), sondern für den exakten Zahlwert "0" (deutsch "null", englisch "zero", nicht "null"). --Payton (Diskussion) 19:03, 19. Feb. 2019 (CET)

Hier hast Du völlig recht. Diese Verwirrung um die fälschliche Gleichsetzung von "Null" und "leer" gibt es immer und immer wieder. Im Artikel Fleißiger Biber (die Biester reden auch nur von 0 und 1) habe ich das im September 2014 entschärft, indem das Band vor dem Aufsetzen des Bibers komplett mit Nullen gefüllt wird. Leere Felder gibt es da also nicht, ein Biber erzeugt sie auch nicht. Er verwendet nur das Alphabet {0,1}. Dann passen auch die Grafiken wieder. ;-) Das wäre hier vielleicht auch eine Möglichkeit. Oder gleich ganz eine andere Grafik. Gruß --Apraphul ^Disk _WP:SNZ 10:17, 20. Feb. 2019 (CET)

Die Verwendung der 0 für das Blank hier mag vielleicht nicht optimal sein scheint mir aber gebräuchlich und legitim zu sein.

Bei Turingmaschinen gibt es eben kein fixes Symbol für das Blank sondern das Blank-Symbol muss für jede Turingmaschine (im 7-Tupel) explizit angegeben werden. Das □ Symbol in der Definition ist also nur ein Platzhalter für das tatsächliche Blanksymbol in den konkreten Turingmaschinen. Wenn man jetzt Turingmaschinen mit binären Alphabet hat scheint es mir dann auch recht natürlich das Alphabet {0,1} zu verwenden und dementsprechend auch die 0 für das Blanksymbol.

Vielleicht bin ich da zu sehr Theoretiker, aber das Zahlensymbol 0 steht in diesem Kontext eben nicht für den Zahlenwert 0 sondern ist ein abstraktes Symbol das entsprechend der Überführungsfunktion verarbeitet wird.

Vorschlag für eine neue Beschriftung der Grafik:

  Konfiguration einer Turingmaschine im Zustand $q_{1}$. Der Lese-Schreibkopf befindet sich über dem grau hervorgehobenen $0$-Symbol. Verwendet man $0$ als das Blank Symbol der Turingmaschine entspricht diese Konfiguration dem Tripel $(q_{1},\epsilon ,011B)$.    

besser wäre natürlich eine neue Grafik die besser auf den Text abgestimmt ist.

LG -- Wdvorak (Diskussion) 15:47, 20. Feb. 2019 (CET)

Sorry, hatte das hier aus den Augen verloren. Wenn oder dass ein "Blank" unbedingt irgendwie als Symbol gekennzeichnet werden muss, um Funktionen so definieren/beschreiben usw., so mag das sein. Ich bin nicht so sehr der Fachmann, als dass ich Deine Argumentation widersprechen könnte oder wollte. Aber rein "machinentechnisch" ist das Blank ein leeres Feld. Soll ein Feld mit einem "Blank beschrieben" werden, so heißt das nichts anderes als: Lösche/leere das Feld. Man brauch das Blank-Zeichen(/Symbol) vielleicht für die Formeln und Definitionen, aber Teil des Alphabets ist es nicht. Ein Blank hilfsweise mit dem Zeichen 0 gleichzusetzen, ist eine relativ gewöhnliche Angelegenheit, ja. Aber jede Beschreibung/jeder Artikel, der das tut, muss auch gewährleisten, dass der Leser nicht denkt, das Zeichen/Symbol 0 sei pauschal immer mit einem leeren Feld gleichzusetzen. Wenn ein Artikel da nicht streng trennt, kann es beim Leser leicht zu diesem Irrtum kommen.

Letzte Anmerkung - nicht, dass wir aneinander vorbeireden: Ich habe nirgendwo in Büchern etwas von Zahlenwerten gelesen (vielleicht überlesen?). Die 0 steht daher sowieso nicht für einen Zahlenwert, sondern ist lediglich ein Zeichen/Symbol (des Alphabets). Oder anders herum ausgedrückt: Das Symbol 0 als Zahlenwert zu interpretieren, soll auch nie Teil meiner Argumentation gewesen sein. :-) Gruß --Apraphul ^Disk _WP:SNZ 08:14, 6. Mär. 2019 (CET)