Characteristics of minimal effective programming systems

DOI10.1007/978-3-642-30870-3_51MaRDI QIDQ2904447zbMATH OpenOpenAlexFDO

Authors Samuel E. III Moelius

Publication date 14 August 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.1372

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45) Recursive functions and relations, subrecursive hierarchies (03D20)

Abstract: The Rogers semilattice of effective programming systems (epses) is the collection of all effective numberings of the partial computable functions ordered such that heta is less than or equal to psi whenever heta-programs can be algorithmically translated into psi-programs. Herein, it is shown that an eps psi is minimal in this ordering if and only if, for each translation function t into psi, there exists a computably enumerable equivalence relation (ceer) R such that (i) R is a subrelation of psi's program equivalence relation, and (ii) R equates each psi-program to some program in the range of t. It is also shown that there exists a minimal eps for which no single such R does the work for all such t. In fact, there exists a minimal eps psi such that, for each ceer R, either R contradicts psi's program equivalence relation, or there exists a translation function t into psi such that the range of t fails to intersect infinitely many of R's equivalence classes.

Recommendations

• scientific article; zbMATH DE number 738897
• Ideals without minimal elements in Rogers semilattices
• On approximate decidability of minimal programs
• Minimal numerations of positively computable families
• A connotational theory of program structure

Cited in

(2)

• A connotational theory of program structure
• Automatic learning from positive data and negative counterexamples

This page was built for publication: Characteristics of minimal effective programming systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904447)