Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

On Approximate Decidability of Minimal Programs

On Approximate Decidability of Minimal Programs On Approximate Decidability of Minimal Programs JASON TEUTSCH, Ben-Gurion University MARIUS ZIMAND, Towson University 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. CCS Concepts: rTheory of computation Computability; Additional Key Words and Phrases: Frequency computation, list approximations, minimal indices, numberings, Kolmogorov complexity ACM Reference Format: Jason Teutsch and Marius Zimand. 2015. On approximate decidability of minimal programs. ACM Trans. Comput. Theory 7, 4, Article 17 (August 2015), http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

On Approximate Decidability of Minimal Programs

Download PDF
16 pages

Loading next page...
 
/lp/association-for-computing-machinery/on-approximate-decidability-of-minimal-programs-kTwlXcWHDt
Publisher
Association for Computing Machinery
Copyright
Copyright © 2015 by ACM Inc.
ISSN
1942-3454
DOI
10.1145/2799561
Publisher site
See Article on Publisher Site

Abstract

On Approximate Decidability of Minimal Programs JASON TEUTSCH, Ben-Gurion University MARIUS ZIMAND, Towson University 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. CCS Concepts: rTheory of computation Computability; Additional Key Words and Phrases: Frequency computation, list approximations, minimal indices, numberings, Kolmogorov complexity ACM Reference Format: Jason Teutsch and Marius Zimand. 2015. On approximate decidability of minimal programs. ACM Trans. Comput. Theory 7, 4, Article 17 (August 2015),

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Aug 31, 2015

There are no references for this article.