The Immortality Problem for Post Normal Systems
- 1 October 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (4) , 594-599
- https://doi.org/10.1145/321356.321367
Abstract
A natural problem, related to the (known unsolvable) halting problem for Post normal systems, arises when one considers, for a given Post normal system, whether the system halts (eventually) on every word over its alphabet. For polygenic systems, this problem is shown to be recursively unsolvable by constructing a reduction from the “Domino Problem.”Keywords
This publication has 1 reference indexed in Scilit:
- Proving Theorems by Pattern Recognition - IIBell System Technical Journal, 1961