On approximate decidability of minimal programs

DOI10.1145/2799561MaRDI QIDQ2828213zbMATH OpenOpenAlexFDO

Authors Jason Teutsch, Marius Zimand

Publication date 24 October 2016

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

frequency computationKolmogorov complexitylist approximationsminimal indicesnumberings

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: An index $e$ in a numbering of partial-recursive functions is called minimal if every lesser index computes a different function from $e$. Since the 1960's it has been known that, in any reasonable programming language, no effective procedure determines whether or not a given index is minimal. We investigate whether the task of determining minimal indices can be solved in an approximate sense. Our first question, regarding the set of minimal indices, is whether there exists an algorithm which can correctly label 1 out of $k$ indices as either minimal or non-minimal. Our second question, regarding the function which computes minimal indices, is whether one can compute a short list of candidate indices which includes a minimal index for a given program. We give some negative results and leave the possibility of positive results as open questions.

Recommendations

• A guided tour of minimal indices and shortest descriptions
• Index sets and universal numberings
• On the Turing degrees of minimal index sets
• On the problem of finding minimal programs for tables
• scientific article; zbMATH DE number 3900734

Cites work

• A guided tour of minimal indices and shortest descriptions
• Algorithmic minimal sufficient statistic revisited
• An easy priority-free proof of a theorem of Friedberg
• An incomplete set of shortest descriptions
• An introduction to Kolmogorov complexity and its applications
• Classical recursion theory. The theory of functions and sets of natural numbers
• Enumerations including laconic enumerators
• Enumerations of the Kolmogorov function
• Game arguments in computability theory and algorithmic information theory
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• Immunity and hyperimmunity for sets of minimal indices
• Index sets and universal numberings
• On approximate decidability of minimal programs
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On the size of machines
• On the Turing degrees of minimal index sets
• Program size in restricted programming languages
• Short lists for shortest descriptions in short time
• Short lists with short programs in short time
• Short lists with short programs in short time -- a short proof
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication

Cited in

(8)

• A guided tour of minimal indices and shortest descriptions
• Short lists with short programs from programs of functions and strings
• Searching for shortest and least programs
• Enumerations including laconic enumerators
• On approximate decidability of minimal programs
• Characteristics of minimal effective programming systems
• On the problem of finding minimal programs for tables
• On the inference of approximate programs

This page was built for publication: On approximate decidability of minimal programs

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