Grundsätzliches Verständnisproblem Turing-Maschine
-
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ß
-
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(231)... klarer?
-
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.
-
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!"
-
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 herGruß
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.
-
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.
-
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 herGleichzeitig 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.
-
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 )
-
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.
-
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.)
-
Theoretisch kann man wunderbar über kontextfreie (oder noch allgemeinere) Sprachen reden. Und in der Theorie ist auch anbn definitiv nicht
kontextfreiedit: 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).
-
CStoll schrieb:
Und in der Theorie ist auch anbn definitiv nicht kontextfrei.
Das ist doch geradezu der Prototyp einer kontextfreien Sprache:
S -> aSb | ab
-
Da habe ich mal wieder schneller geschrieben als mitgedacht - richtig muß es heißen: "anbn ist definitiv nicht regulär"