ON A QUANTITATIVE NOTION OF UNIFORMITY

Article type: Research Article

Authors: Kaufmann, Susanne | Kummer, Martin

Affiliations: Institut für Logik, Komplexität uud Deduktionssysteme, Universität Karlsruhe, D-76128 Karlsruhe. Germany. E-mail: {srogina;kummer}@ira.uka.de

Abstract: One topic arising in recent research on “Bounded Query Classes” is to consider quantitative aspects of recursion theory, and in particular various notions of parameterized recursive approximations of sets. An important question is, for which values of the parameters – depending on the type of approximation – the approximated set is necessarily recursive. Beigel's Nonspeedup Theorem, Rummer's Cardinality Theorem and Trakhtenbrot's Theorem provide answers using nonuniform constructions. This paper investigates to which extend these constructions can be made uniform. Beigel's Nonspeedup Theorem is equivalent to the statement that every branch of a recursively enumerable tree of bounded width is recursive. There is no algorithm which computes a branch from the index of the tree, but there are nontrivial positive results by weakening the requirements as follows: For some fixed number k, an algorithm is wanted which, given an index of a tree, outputs a list of k programs such that at least one of them computes a branch of the tree up to finitely many errors. What is the least k for which this works? In this paper it is shown that, for recursively enumerable trees of width at most n, the least possible k is 2n−1. For trees arising from Trakhtenbrot's Theorem with parameters m, n, the optimal value is k = n − m + 1. In addition, several other, related classes of trees are investigated.

DOI: 10.3233/FI-1996-25106

Journal: Fundamenta Informaticae, vol. 25, no. 1, pp. 59-78, 1996