Monogenic Post Normal Systems of Arbitrary Degree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Monogenic Post Normal Systems of Arbitrary Degree

Full text

Pdf (677 KB)

Source

Journal of the ACM (JACM) archive
Volume 13 , Issue 3 (July 1966) table of contents

Pages: 359 - 363

Year of Publication: 1966

ISSN:0004-5411

Author

Philip K. Hooper

Computation Laboratory, Harvard University, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 16, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321341.321344 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.1 Models of Computation
Subjects: Bounded-action devices (e.g., Turing machines, random access machines)