On Approximate Decidability of Minimal Programs
Jason Teutsch, Marius Zimand · ACM Transactions on Computation Theory · 2015
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 1960s, 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 that can correctly label 1 out of k indices as either minimal or nonminimal. Our second question, regarding the function that computes minimal indices, is whether one can compute a short list of candidate indices that includes a minimal index for a given program. We give negative answers to both questions for the important case of numberings with linearly bounded translators.