Fleißiger Biber

12/08/2014 - 21:22 von Hans-Peter Diettrich | Report spam
Ich weiß, das Thema wurde schon vielfach untersucht, mir geht es heute
aber um Probleme drum herum, insbesondere kombinatorische.

Zuerst habe ich mich bei der Berechnung der möglichen Turing-Maschinen
mit 5 Zustànden furchtbar verhauen. Wenn jede Maschine 5 Zustànde (plus
Halt) hat, und auf ihrem Band nur 0 oder 1 stehen kann, dann sind dafür
10 Aktionen zu definieren. Wenn jede Aktion aus einem neuen Zustand
(H,1..5), einer Ausgabe (0,1,N) und einer Kopfbewegung (L,R)[1] besteht,
dann hàtte ich dazu 10*6*3*2 mögliche Maschinen erwartet - das scheint
aber nicht zu stimmen?

[1] Keine Kopfbewegung erscheint mir hier unproduktiv zu sein.

Dann möchte ich die Zahl der zu untersuchenden Maschinen begrenzen. Dazu
sollen alle Maschinen aussortiert werden, die weniger als 6 erreichbare
Zustànde haben, oder in einer Sackgasse (kein anderer Zustand
erreichbar) landen können, oder die (mit Vertauschung der Zustànde)
àquivalent sind. Gibt es einen Algorithmus, mit dem sich alle
verbleibenden Maschinen aufzàhlen lassen?

Gibt es noch weitere Kriterien, mit deren Hilfe sich die Zahl der zu
untersuchenden Maschinen reduzieren ließe?


Als erstes Verfahren fiel mir ein, daß aus jedem Zustand Z (außer Halt
und dem letzten Zustand) mindestens ein Zustand Z+1 erreichbar sein muß,
optional noch Z+2, und keinesfall ein noch höherer Zustand. Damit wàre
ein zusammenhàngender Graph ohne (direkte) Sackgassen gewàhrleistet, und
etliche Permutationen wàren schon ausgeschlossen. Aber da gibt es doch
sicher noch was besseres?

DoDi
 

Lesen sie die antworten

#1 Hans-Peter Diettrich
19/08/2014 - 03:34 | Warnen spam
Hans-Peter Diettrich schrieb:

Dann möchte ich die Zahl der zu untersuchenden Maschinen begrenzen. Dazu
sollen alle Maschinen aussortiert werden, die weniger als 6 erreichbare
Zustànde haben, oder in einer Sackgasse (kein anderer Zustand
erreichbar) landen können, oder die (mit Vertauschung der Zustànde)
àquivalent sind. Gibt es einen Algorithmus, mit dem sich alle
verbleibenden Maschinen aufzàhlen lassen?



Inzwischen habe ich es geschafft, die 6^10 möglichen Maschinen auf rd.
130000 strukturell unterschiedliche Maschinen zu reduzieren. Zu jeder
dieser Maschinen gibt es noch 2^10 Varianten (Bandoperationen), die zu
untersuchen wàren. Ein Schnelltest braucht dafür jeweils ca. 1 Sekunde,
um die hoffnungslosen Kandidaten auszusortieren, die vorzeitig anhalten
oder das Band mit jedem Schritt in die gleiche Richtung verschieben. Für
die Maschinen mit regulàren Endlos-Schleifen gibt es einen
Erkennungs-Algorithmus, den ich auf die verbleibenden Maschinen ansetzen
werde. Mal sehen, was dann noch übrigbleibt.

Zu den (angeblich) 40 irregulàren Maschinen habe ich noch keine nàheren
Informationen gefunden, so daß ich nicht sagen kann, ob sich diese
Anzahl weiter reduzieren làßt. Weiß jemand mehr darüber?

DoDi

Ähnliche fragen