Monogenic Post Normal Systems of Arbitrary DegreeMonogenic Post Normal Systems of Arbitrary Degree

Access Restriction
Subscribed

 Author Hooper, Philip K. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1966 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract From an arbitrary Turing machine, $\textit{Z},$ a monogenic Post normal system, $\textit{v}(\textit{Z}),$ is constructed. It is then shown not only that the halting problem for $\textit{Z}$ is reducible to that of $\textit{v}(\textit{Z})$ but also that the halting problem for $\textit{v}(\textit{Z})$ is reducible to that of $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1966-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 13 Issue Number 3 Page Count 5 Starting Page 359 Ending Page 363

Open content in new tab

Source: ACM Digital Library