Retro Computer Laboratory

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.

====== 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 [[hasenjaeger:mini-wang|Mini-Wang]] von 1965.
(Die Register-Turing-Maschine [[hasenjaeger:utm84|UTM-84]] wird noch nachgetragen).

Der Text ist derzeit nur als PDF verfügbar: {{:hasenjaeger:tmindex-20120910.pdf|TM-Index}}