Spezielles Halteproblem

22/10/2014 - 13:22 von Hans-Peter Diettrich | Report spam
Frage: wieviele Schritte kann eine Turingmaschine (TM) auf einem
beschrànkten Band ausführen, bevor sie anhàlt?

Die möglichen Kombinationen der Zellen (Bits) auf diesem Band sind
bekannt, es sind K=AnzahlSymbole^AnzahlZellen. Auch die Anzahl der
möglichen Zustànde (Z) ist bekannt, ich bin mir aber nicht sicher, wie
die in die maximal mögliche Schrittzahl eingeht. Kann mir da jemand
weiterhelfen?

Meine Idee: Wenn die TM denselben Inhalt des Bandes im gleichen Zustand
erreicht, dann wird diese Konfiguration immer wieder auftreten, d.h. die
Maschine hàlt nie an. Die maximal mögliche Schrittzahl müßte demnach
kleiner sein als K*Z, wenn die Maschine irgendwann anhalten soll. Ist
das so richtig, oder habe ich was übersehen? Muß auch noch die Position
des Kopfes auf dem Band berücksichtigt werden, dann kàme nochmal der
Faktor AnzahlZellen hinzu?

Oder fàllt jemand eine kleinere Schranke ein?

Der Nachweis, daß eine solche TM nicht anhàlt, vereinfacht sich dann auf
den Nachweis, daß sie nach der maximal möglichen Schrittzahl nicht anhàlt.


Oder kennt jemand eine Prozedur, mit der sich eine Endlosschleife auf
einem beschrànkten Band mit weniger Aufwand (Anzahl Schritte...)
nachweisen làßt?

Hintergrund: Dieses spezielle Problem ist mir bei der Analyse von
allgemeinen Turingmaschinen aufgefallen. Làßt man so eine Maschine
loslaufen, dann làßt sich recht einfach ermitteln, welche Zustànde sie
regelmàßig einnimmt, d.h. daß derselbe Zustand nach der gleichen Anzahl
von Schritten (dS) und gleicher Distanz des Kopfes (dH) erreicht wird -
was das Vorhandensein einer Schleife nahelegt. Befindet sich der Kopf
zudem in der ursprünglichen Position (dH=0), dann könnte es sich um eine
Endlosschleife auf dem Bereich des Bandes handeln, der wàhrend einer
Iteration überhaupt gelesen wird. Und genau diesen Fall möchte ich gerne
erkennen.

DoDi
 

Lesen sie die antworten

#1 Robin Koch
22/10/2014 - 23:04 | Warnen spam
Am 22.10.2014 um 13:22 schrieb Hans-Peter Diettrich:

Frage: wieviele Schritte kann eine Turingmaschine (TM) auf einem
beschrànkten Band ausführen, bevor sie anhàlt?



Klingt nach einem zeitlichen Pendant zum Busy Beaver!?

Robin Koch

Ähnliche fragen