Proving properties of a ring of finite-state machines
type: Item
instance of: scholarly article
title: Proving properties of a ring of finite-state machines
zbMATH Open document ID: 0664.68048
DOI: 10.1016/0020-0190(88)90211-6
author: Ichiro Suzuki
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 4087021
zbMATH Keywords: simulation of Turing machine
zbMATH Keywords: halting problem
zbMATH Keywords: finite automaton
zbMATH Keywords: unidirectional ring
zbMATH Keywords: verification
reviewed by: U. Klemm
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90211-6
OpenAlex ID: W2066611459
cites work: Q4124327
description: scientific article; zbMATH DE number 4087021