Grundsätzliches Verständnisproblem Turing-Maschine
-
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.
-
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"