TM-Index

Shannon hat vorgeschlagen, das Zustands-Symbol-Produkt einer Turing-Maschine als Maß für die Einfachheit vorgeschlagen, da mit mehr Symbolen auf dem Band die Anzahl der Zustände reduziert werden kann. Da im Laufe der Zeit Maschinen mit mehreren Bändern dazukamen und insbesondere jede klassische Turing-Maschine mit einem Band in eine mit zwei Bändern und nur einem Zustand transformiert werden kann, wird eine Zahl „„TM-Index““ vorgeschlagen, die Turing-Maschinen mit einem und mehreren Bändern vergleichbar macht und auch Besonderheiten wie nur einmal schreibbare Bänder umfasst. Der folgende Artikel beschreibt diesen Ansatz und gibt etliche Beispiele, darunter Hasenjaegers Mini-Wang von 1965. (Die Register-Turing-Maschine UTM-84 wird noch nachgetragen).

Der Text ist derzeit nur als PDF verfügbar: TM-Index