Switch to: References

Citations of:

A guided tour of minimal indices and shortest descriptions

Marcus Schaefer

Archive for Mathematical Logic 37 (8):521-548 (1998)

Add citations

You must login to add citations.

An incomplete set of shortest descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.details The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete degree (...) Download Export citation Bookmark
Learning correction grammars.Lorenzo Carlucci, John Case & Sanjay Jain - 2009 - Journal of Symbolic Logic 74 (2):489-516.details We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars capture the observable fact that (...) Download Export citation Bookmark 1 citation
Parsimony hierarchies for inductive inference.Andris Ambainis, John Case, Sanjay Jain & Mandayam Suraj - 2004 - Journal of Symbolic Logic 69 (1):287-327.details Freivalds defined an acceptable programming system independent criterion for learning programs for functions in which the final programs were required to be both correct and "nearly" minimal size, i.e., within a computable function of being purely minimal size. Kinber showed that this parsimony requirement on final programs limits learning power. However, in scientific inference, parsimony is considered highly desirable. A lim-computablefunction is (by definition) one calculable by a total procedure allowed to change its mind finitely many times about its output. (...) Download Export citation Bookmark 1 citation
On the Turing degrees of minimal index sets.Jason Teutsch - 2007 - Annals of Pure and Applied Logic 148 (1):63-80.details We study generalizations of shortest programs as they pertain to Schaefer’s problem. We identify sets of -minimal and -minimal indices and characterize their truth-table and Turing degrees. In particular, we show , , and that there exists a Kolmogorov numbering ψ satisfying both and . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, , is 2-c.e. but not co-2-c.e. Some open problems are left for the (...) reader. (shrink) Download Export citation Bookmark 1 citation
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.details We extend Meyer's 1972 investigation of sets of minimal indices. Blum showed that minimal index sets are immune, and we show that they are also immune against high levels of the arithmetic hierarchy. We give optimal immunity results for sets of minimal indices with respect to the arithmetic hierarchy, and we illustrate with an intuitive example that immunity is not simply a refinement of arithmetic complexity. Of particular note here are the fact that there are three minimal index sets located (...) Download Export citation Bookmark 1 citation

1