Vol. 46, No. 1, 1973

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 294: 1
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
On orders of translations and enumerations

John Paul Helm, Albert Ronald da Silva Meyer and Paul Ruel Young

Vol. 46 (1973), No. 1, 185–195
Abstract

A basic result of intuitive recursion theory is that a set (of natural numbers) is decidable (recursive) ffl it can be effectively enumerated in its natural order (of increasing magnitude). The chief theorems of this paper give simple, but very basic facts relating to enumerations in natural order of magnitude and the extent to which translations must preserve the orders of the sets being enumerated. Under very general conditions for what constitutes a programming system for enumerating the recursively enumerable (r.e.) sets, we prove in Theorem 1 that not every recursive set is “best” enumerated in its natural order, and we later show that under these same general conditions, in every programming system, every recursive set is enumerable in its natural order. We accomplish the latter result by extending Rogers’ Isomorphism Theorem to a result which asserts that under these same general conditions, every programming system can be effectively translated into any other in a manner which preserves the order of the sets being enumerated (Theorems 4 and 5). In fact, we show that for every translator, t, there is an order preserving pretranslator, p, such that t is order-preserving modulo p; i.e., t p is an order preserving translator. In addition, the restriction of the original programming system to the recursive set {range p} is a standard programming system on which t is order-preserving. Along the way we establish the existence of sets best enumerated in their natural order and, for every r.e. set, the existence of bad orders for enumerating the set. All proofs are fairly straightforward.

Mathematical Subject Classification
Primary: 02F25
Milestones
Received: 23 February 1972
Revised: 9 October 1972
Published: 1 May 1973
Authors
John Paul Helm
Albert Ronald da Silva Meyer
Paul Ruel Young