Grundsätzliches Verständnisproblem Turing-Maschine

Hallo,

ich fürchte ich hab ein grundlegendes verständnisproblem bzgl. turing-maschinen... eine turing maschine besteht ja aus einem (unendlich) langen band auf dem ein lese/schreibkopf hin und her fährt, der in verschiedene zustände gebracht werden kann...
angenommen ich will den inhalt zweier zellen mit nr. 4 und 12 vergleichen... ich bewege also den kopf zu zelle 4 (ok) und lese das symbol (ok)... jetzt muss ich zum vergleichen das gelesene symbol irgendwo zwischenspeichern, aber wie soll das funktionieren? der kopf besitzt ja keinen speicher (oder?), sondern nur ein paar zustände und ich weiß ja nicht in welchem zustand ich mich gerade befinde (oder?), sodass ich das gelesene symbol durch einen zustand repräsentieren könnte (es sei denn es könnte mehrere zustandsübergänge für ein und dasselbe symbol geben, was ja nicht erlaubt ist (oder?))...
beispiel: der kopf befindet sich in zusatnd X, ich gehe zu zelle nr. 4 und lese das symbol. angenommen ich will das symbol "addieren", dann gehe ich also in den zustand "addiere" und lese weiter vom band. angenommen ich will das symbol "vergleichen", dann gehe ich also in den zustand "vergleiche" und lese weiter vom band. aber die maschine kann ja beim lesen des symbols noch nicht wissen ob sie "addieren" oder "vergleichen" soll...

Ich vermute es liegt hier ein grundsätzliches verständnisproblem vor, aber ich komm nicht weiter...

wär nett, wenn mir das kurz jemand erläutern könnte... (ich hoffe mal ich hab mein problem einigermaßen verständlich ausgedrückt)

danke für die aufmerksamkeit

Jester

Warum sollte es keinen Zustand "vergleiche mit x" für einen wert x geben?

Krux

der Zustand der Turingmaschiene ist dessen Speicher, und so kannst du ihn auch nutzen.

Aber die Turingmaschiene ist fast schon wieder aus meinem Kopf verschwunden

thordk

turingmaschinen werden sehr komplex, wenn man große alphabete verwendet und so "komplizierte" methoden wie "speicherzellenvergleich" implementieren möchte.

man darf sich eine turingmaschine nicht wie einen pc vorstellen. ein pc ist eine sehr stark abstrahierte universelle turingmaschine. bei der einfachen turingmaschine ist das band ein reiner speicher und das programm ist eine menge an zuständen, die zum gewünschten ziel führen. wie jester bereits sagte, warum kann es keinen zustand "vergleiche mit x" geben.

du hättest also beispielsweise so eine folge von zuständen:
z1: "wenn gelesen "4" gehe z2" (hier soll der kopf auf zelle 4 stehen, wie er dahinkommt ist unwichtig)
z2: "gehe rechts, dann z3"
usw.
z8: "gehe rechts, dann z9" (z9 ist die 12. zelle)
z9: "wenn gelesen "4", z10"
z9: "wenn "nicht" gelesen "4", z11" (negation in dem sinne gibt es nicht, das wäre eine weitere folge von zuständen)
z10: "schreibe "korrekt""
z11: "schreibe "falsch""

Hallo

thordk schrieb:

ein pc ist eine sehr stark abstrahierte universelle turingmaschine.

Ein pc ist keine Turingmaschine:
Eine Turingmaschine hat unendlichen (Band-)Speicher
- ein pc hat nur endlichen Speicher.

Die Turingmaschine ist ein reines Gedankenkonstrukt, in einem
Universum mit endlich vielen Teilchen gibt es nur endliche Automaten.

Existierende Computer können nicht mehr als reguläre Ausdrücke erkennen
(Chomsky-Hierarchie).

Gruß

Jester

kleine Bemerkung schrieb:

Ein pc ist keine Turingmaschine:
Eine Turingmaschine hat unendlichen (Band-)Speicher
- ein pc hat nur endlichen Speicher.

Es gibt auch bandbegrenzte Turingmaschinen.

edit: Vielleicht noch ne kleine mathematische Modellierung um das mit den Zuständen besser in den Griff zu kriegen. Bezeichnen wir mal mit B:={0,1,...,255} die Werte, die ein Byte annehmen kann.

Wenn Du jetzt als Zustandsmenge B nimmst, dann haste einen Rechner mit einem Byte Speicher. Nimmst Du BxB, dann werden die Zustände ja durch 2 Zahlen beschrieben, etwa (17,25). Also hast Du nun zwei Bytes. Eine Turingmaschine mit k Bytes Speicher baut man also, indem man als Zustandsmenge B^k nimmt. Ein Rechner mit 2GB Speicher besitzt also als Zustandsmenge B⁽²31)... klarer?

Apollon

kleine Bemerkung schrieb:

thordk schrieb:

ein pc ist eine sehr stark abstrahierte universelle turingmaschine.

Ein pc ist keine Turingmaschine

Das ist richtig. Ein PC ist eine Registermaschine.

kleine Bemerkung schrieb:

Existierende Computer können nicht mehr als reguläre Ausdrücke erkennen
(Chomsky-Hierarchie)

Das stimmt nicht. Kontextfreie- und Teilmenge von Kontextsensitiven Sprachen koennen sie auch erkennen. Man denke nur an die C++-Compiler.

Jester

Apollon schrieb:

Das stimmt nicht. Kontextfreie- und Teilmenge von Kontextsensitiven Sprachen koennen sie auch erkennen. Man denke nur an die C++-Compiler.

Nene, das ist mal wieder so ne grandiose Endlichkeitsargumentation a la "Eigentlich ist ja alles endlich und deswegen ist alles regulär und alles kann in O(1) berechnet werden und P=NP=PSPACE und Unentscheidbarkeit gibt's auch nicht -- weil ich hab die Theorie nämlich verstanden!"

thordk

Apollon schrieb:

Das ist richtig. Ein PC ist eine Registermaschine.

registermaschinen können turingmaschinen simulieren und somit auch alle probleme lösen, die eine turingmaschine lösen kann. da eine registermaschine alles kann, was ein rechner kann, kann ein rechner also auch eine turingmaschine simulieren.

das reicht mir als definition eines rechners als turingmaschine.

die unendlichkeit des bandes gehört zwar zur definition der turingmaschine, ist aber keine zwingende voraussetzung. eine genauere spezifikation wäre "das band muss lang genug sein".

die einzige schwierigkeit sind probleme, die sich nur durch eine unendliche zustandsmenge kodieren lassen

super, ich danke euch! jetzt ist mir einiges klarer!

Hallo

wie schon gesagt:

Existierende PCs sind weder Turing-Maschinen noch Registermaschinen noch
Stapelmaschinen, und sie können weder kontextfreie noch kontextsensitive
Sprachen erkennen.
Denn in allen diesen Fällen wäre ein unendlicher Speicher zwingende
Voraussetzung.

Alles, was PCs können, ist die Erkennung regulärer Sprachen.

Tut mir ja leid, aber mehr gibt die materielle Seite unseres Universums
womöglich nicht her

Gruß

PS. Eine Turingmaschine mit begrenztem Bandspeicher ist äquivalent zu einem
endlichen Automaten.
Man muß dazu nur den endlichen Bandspeicher in endlich viele Zustände codieren,
qed.

CStoll

Mal zurück zum ursprünglichen Problem - Vergleichen oder Addieren von zwei Werten auf dem Band:

Es gibt auch Mehr-Band-Turingmaschinen (und Verfahren, um auf einer normalen TM die Arbeitsweise einer Mehr-Band-TM nachzubilden). Und mit drei Bändern sind die normalen Rechenoperationen beinahe trivial zu lösen:
- schreibe einen der Operanden auf Band 2
- setze die Leseköpfe von Band 1 und 2 an den Anfang der beiden Operanden
- addiere die einzelnen Stellen des Operanden und schreibe die Summe auf Band 3
(oder vergleiche die Operanden stellenweise miteinander)

Zur Einordnung der heute üblichen Rechner:
Ja, ein PC hat nur endlichen Speicher und könnte deshalb in einigen Fällen an seine Grenzen kommen. Aber von der Arbeitsweise entspricht er eher einer (platzbegrenzten) Register- als einer Turingmaschine.

Jester

Bemerkung schrieb:

wie schon gesagt:

Existierende PCs sind weder Turing-Maschinen noch Registermaschinen noch
Stapelmaschinen, und sie können weder kontextfreie noch kontextsensitive
Sprachen erkennen.
Denn in allen diesen Fällen wäre ein unendlicher Speicher zwingende
Voraussetzung.

Alles, was PCs können, ist die Erkennung regulärer Sprachen.

Tut mir ja leid, aber mehr gibt die materielle Seite unseres Universums
womöglich nicht her

Gleichzeitig müßte Dir aber klar sein, dass Du damit alle interessanten und wichtigen Analysewerkzeuge aus der Komplexitätstheorie über den Haufen wirfst. Und warum? -- Was nützt einem Deine "Erkenntnis"? ... kann ich damit jetzt schnelle Algorithmen bauen?

Hier nützt die Abstraktion einfach mehr als sie schadet. In diesem Fall ist die Abstraktion einfach näher dran an der Realität.

ronny

würde man unendlich viel speicher für kontextsensitivität benötigen wären auch menschen nicht dazu in der lage

fakt ist - begrenze kontextsensitivität kann man mit begrenzten mitteln realisieren

und genau das tun alle kontextsensitiven realen systeme ( auch menschen )

Jester

Die Argumentation läuft doch über Endlichkeit. Jede endliche Sprache ist regulär. Da alles endlich ist, ist alles regulär.

Das Problem dabei ist, dass dadurch Problemstrukturen und Unterschiede verschleiert werden, man also dadurch tatsächlich weniger sieht. Ein Grund, warum ich eine solche Argumentation für ziemlich doof halte.

minhen

r0nny schrieb:

würde man unendlich viel speicher für kontextsensitivität benötigen wären auch menschen nicht dazu in der lage

fakt ist - begrenze kontextsensitivität kann man mit begrenzten mitteln realisieren

und genau das tun alle kontextsensitiven realen systeme ( auch menschen )

Es geht ja eben um die Auswirkung der begrenzten Mittel. Denn dadurch das z.B. die Implementierung eines Kellers notgedrungen endlich sein muss, kann dieser auch nicht unendlich wachsen. Das gilt also bereits für kontextfreie Sprachen. Einfaches Beispiel a^n b^n. Diese Sprache kann ein realer Kellerautomat nur erkennen wenn für das n eine Begrenzung vorliegt, da das n sonst bei Unendlichkeit irgendwann die endliche Kapazität des Kellers übersteigen würde. Durch eine solche Beschränkung ist die beschriebene oder beschreibbare Sprache aber endlich. Und jede endliche Sprache wiederum ist regulär (d.h. anschaulich, dass sie sich zu einem endlichen Automaten kompilieren lässt).
Das heißt, natürlich kann man auch kontextfreie und -sensitive Systeme implementieren. Die dadurch beschreibbare Sprachen sind aber aufgrund der Endlichkeit eben regulär und nicht kontextfrei oder höher.
Da diese Endlichkeit aber dennoch sehr groß sein kann, ist es natürlich äußerst unpraktisch die Sprachen regulär zu beschreiben.

Das gilt so natürlich auch für Menschen und ist eine der Gründe, weshalb man auch argumentieren kann, das natürliche Sprache regulär ist. (Man kann, wenn man will, weniger streng aber auch argumentieren, dass natürliche Sprache noch nicht mal vom Typ 0 ist.)

CStoll

Theoretisch kann man wunderbar über kontextfreie (oder noch allgemeinere) Sprachen reden. Und in der Theorie ist auch aⁿbⁿ definitiv nicht ~~kontextfrei~~ edit: regulär.

Erst wenn es darum geht, ein theoretisches Maschinenmodell (das mit unbegrenztem Speicher etc hantieren müsste) in der Praxis nachzubauen, stößt du auf die physikalischen Grenzen. Aber dann reicht es in den meisten Fällen aus, platzbeschränkte Maschinen zu betrachten (und die betrachteten Maschinen können zwar sehr viel Platz verbraten, aber für ein endlich langes Wort in der Regel auch nur endlich viel davon).

Jester

CStoll schrieb:

Und in der Theorie ist auch aⁿbⁿ definitiv nicht kontextfrei.

Das ist doch geradezu der Prototyp einer kontextfreien Sprache:
S -> aSb | ab

CStoll

Da habe ich mal wieder schneller geschrieben als mitgedacht - richtig muß es heißen: "aⁿbⁿ ist definitiv nicht regulär"