Characteristics of minimal effective programming systems

DOI10.1007/978-3-642-30870-3_51zbMATH Open1357.68042arXiv1204.1372OpenAlexW3102148720MaRDI QIDQ2904447FDOQ2904447

Publication date: 14 August 2012

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

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.

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

Recommendations

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)

Cited In (2)

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)