Proving properties of a ring of finite-state machines (Q1115609): Difference between revisions

Es wird gezeigt: Eine einsinnige Kreisschaltung von \(n>1\) endlichen Automaten fester, insbesondere von n unabhängiger Konfiguration simuliert die ersten n Schritte einer TURING-Maschine, nach denen sie entscheidet, ob eine gegebene TM, deren Bild sie ist, mit leerem Band gestartet, nach n Schritten anhält oder weiterläuft. Der Beweis der Aussage: ``Die Schaltung aus n Gliedern zeigt `Weiterlaufen' an'' für alle \(n>1\) ist somit auf das Nichthalteproblem zurückgeführt. Für die Klasse der Ringschaltungen von Automaten - und deren getreue Implementationen als Wanderungen auf zyklischen Listen - existieren also Aussagen, die nicht einmal partiell entscheidbar sind.