Monogenic Post Normal Systems of Arbitrary Degree
- 1 July 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (3) , 359-363
- https://doi.org/10.1145/321341.321344
Abstract
From an arbitrary Turing machine, Z , a monogenic Post normal system, v ( Z ), is constructed. It is then shown not only that the halting problem for Z is reducible to that of v ( Z ) but also that the halting problem for v ( Z ) is reducible to that of Z . Since these two halting problems are of the same degree, the halting problem for the normal system can have an arbitrary (recursively enumerable) degree of undecidability.Keywords
This publication has 0 references indexed in Scilit: