Grundsätzliches Verständnisproblem Turing-Maschine

[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

[flanders]

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

[Bemerkung]

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"