Monogenic Post Normal Systems of Arbitrary Degree
Philip K. Hooper · Journal of the ACM · 1966
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.