Turing-Maschine platzbeschränkt, zeitbeschränkt?
- Ist eine platzbeschränkte Turing-Maschine immer zeitbeschränkt?
- Ist eine zeitbeschränkte Turing-Maschine immer platzbeschränkt?
Ja/Nein - Antwort
3 Antworten
Platz kann wiederverwendet werden, Zeit nicht.
Ich kann nicht mehr Zellen eines Bandes besuchen, als ich Zeit (Rechenschritte) verbrauche. GGf. zusätzlich vorhandener Platz bleibt zwingend ungenutzt. (Zu 2.)
Umgekehrt (also bei Platzbeschränkung) gilt, die Zahl der Konfigurationen ist beschränkt. Die gleiche Konfiguration mehrfach zu sehen bedeutet, eine Endlosschleife zu haben. Schließe ich diesen Fall kategorisch aus, so ergibt sich aus der Platzbeschränktheit automatisch eine Zeitbeschränktheit. (Zu 1.)
Warum ist es mitunter sinnvoll eine Endlosschleife auszuschließen?
Hm weiß nicht genau.
Was hältst du von:
- Auch auf beschränktem Platz kannst Du unendlich lange rechnen
- In beschränkter Zeit kannst Du auch nur endlich viel Platz benötigen
Eine NTM M akzeptiert ein w∈L(M) mit
- der Zeitbeschränkung t∈R genau dann, wenn die kürzestes Erfolgsrechnung ⌈t⌉ Schritte hat
"Zeit" ist also eine "Anzahl an Schritten".
Da in einer festen Anzahl an Schritten auch nur ein endlicher Teil des Bandes benutzt werden kann ist sie automatisch Platzbeschränkt.
Schau dir die Definitionen und Folgerungen hier
http://fgi1-skript.de/zeit-und-platzkomplexitaet/
noch mal an. Ich würde interpretieren das Zeitbeschränkung immer Platzbeschränkung nach sich zieht, da in endlicher Zeit nur endlicher Platz belegt werden kann. Der umgekehrte Fall gilt meiner Ansicht nach nicht, da eine Endlosschleife auch auf einem endlichen Platz ablaufen kann.
Ein formaler Beweis ist das natürlich nicht, aber du solltest damit weiter machen können.
Bitte lies: https://www.gutefrage.net/frage/turing-maschine-platzbeschraenkt-zeitbeschraenkt#comment-329780185
Zeit- oder platzbeschränkte Turingmaschinen sind keine Computer im Sinne Turings und seiner Ergebnisse (!).
Das hat mit der Definition nichts zu tun. Zeitbeschränkt heißt ja nur, nach einer Höchstzahl an Schritten wird ein Eingabewort verworfen oder akzeptiert. Und innerhalb dieser Höchstzahl können nur endlich viele Ausgaben erfolgen (in jedem Schritt eine), d.h. eine zeitbeschränkte Turingmaschine ist platzbeschränkt. Die Umkehrung muß meiner Ansicht nach nicht gelten, insbesondere z.B. bei einer Endlosschleife.
Insbesondere bedeutet "Platzbeschränkt" ja gerade, dass vom endlosen verfügbaren Speicher nur ein endlicher, vorher definierter Teil verwendet wird. Deshalb habe ich ja gerade die Definitionen verlinkt.
Völlig richtig. Dennoch ist wichtig zu wissen, dass Turings Ergebnisse bewiesen wurden unter der Nebenbedingung, dass das Band der Turingmaschine nach beiden Seiten hin unendlich viel Plätze aufweist.
Mit anderen Worten: Beschränkte "Turingmaschinen" sind keine Maschinen im Sinne Turings und der Definition des Berechenbarkeitsbegriffs.
Nein, die Forderung der Beschränkung ist eine zusätzliche mögliche Eigenschaft einer Turingmaschine, so wie "Monotonie" oder "Differenzierbarkeit" zusätzliche Eigenschaften von Funktionen sein können. Und auf diese mögliche zusätzliche Eigenschaft bezieht sich die Frage.
ich hab schon das problem mit dem begriff unendlich der hier irgendwie als Beweis geführt wird . also etwas was es so eh nicht gibt , den unendlich ist eine abstraktion eines zustandes der nicht umsetzbar ist . auch die endlosschleife sehe ich nicht als möglich , irgendwann wird irgendwas überschrieben sonst wäre es keine schleife :) ein kreis mag ja eine undenliche linie sein , aber beim zeichnen hab ich ein anfang und ein ende . für mich taschenspielertricks . funktioniert nur in der abstraktion des nicht seins . also gibt es das auch nicht . sonst ist halt jeder traum auch wirklichkeit , weil es ist ja passiert , aber halt nur im traum .
Mathematiker kennen sogar unendlich viele unterschiedliche Unendlichkeiten und können auch sehr gut damit umgehen.
Turingmaschinen sind ein mathematisches Konzept, welches nur von der allereinfachsten dieser vielen Unendlichkeiten Gebrauch macht: der geordneten Menge aller ganzen Zahlen.
Da eine Turingmaschine keine echte Maschine ist, sondern nur eine gedachte, kann man o.E. annehmen, dass sie für jeden Schritt gar keine Zeit benötigt.
Nebenbei: Das Band einer Turingmaschine denkt man sich immer unendlich groß, d.h. es gibt für jede ganze Zahl eine Position auf dem Band.