Browse Prior Art Database

CHARACTERIZING THE ORDERS CHANGED BY PROGRAM TRANSLATORS

IP.com Disclosure Number: IPCOM000128258D
Original Publication Date: 1974-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 1 page(s) / 12K

Publishing Venue

Software Patent Institute

Related People

Maragaret Shay: AUTHOR [+4]

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 com-putable permutations which break into finite cycles.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 67% of the total text.

Page 1 of 1

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

CHARACTERIZING THE ORDERS CHANGED BY PROGRAM TRANSLATORS

by Maragaret Shay and Paul Young

Computer Sciences and Mathematics Departments Purdue University Lafayette, In(liana 47907

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 com-putable permutations which break into finite cycles.

In [Ji-M-Y], it is shown that every translator from one programming sytem for the recursively enumerable (r.e.) sets to another such programming system must preserve every order of enumeration of every r.e. set on infinitely many of the programs which enumerate the set in the given order. It was also conjectured there that for every translator, many nontrivial sets nevcr have their order of enumeration changed by the translation of any of their This conjecture is false, although "nearly" true. Specificallyin this paper we show that given any r.e. set of effective permutations which break into finite cycles, we can easily build a trans- lalor which changes every (infinite) order of enumeration by every per-, mmtation in this set. On the if a program enumerates a set sufficiently slowly, then no tr.-insiol:Aon of the program can change the order of enumeration by a permutation which has an infinite cycle. Thus for any translation, many sets have al.1- of th...