Characterizing the orders changed by program translators

Margaret Shay and Paul Ruel Young

Vol. 76 (1978), No. 2, 485–490

DOI: 10.2140/pjm.1978.76.485

Abstract

The ways in which translators from one programming system for the recursively enumerable sets to another such programming system can change the orders of the sets being translated are characterized using the computable functions which permute infinitely many initial segments.

Mathematical Subject Classification 2000

Primary: 03D20

Secondary: 68B05

Milestones

Received: 16 October 1975

Revised: 23 November 1977

Published: 1 June 1978