Index Sets and Universal Numberings

DOI10.1007/978-3-642-03073-4_28zbMath1268.03059OpenAlexW1569526140MaRDI QIDQ3576059

Jason Teutsch, Sanjay Jain, Frank Stephan

Publication date: 28 July 2010

Published in: Mathematical Theory and Computational Practice (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03073-4_28

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Other Turing degree structures (03D28)

Related Items (3)

An incomplete set of shortest descriptions ⋮ Program Self-reference in Constructive Scott Subdomains ⋮ Program self-reference in constructive Scott subdomains

Cites Work

• Unnamed Item
• A guided tour of minimal indices and shortest descriptions
• Classical recursion theory. The theory of functions and sets of natural numbers
• Classical recursion theory. Vol. II
• Extremes in the degrees of inferability
• On the Turing degrees of minimal index sets
• Kolmogorov complexity and the Recursion Theorem
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• A proof of Beigel's cardinality conjecture
• Frequency computations and the cardinality theorem
• Program size in restricted programming languages
• A cardinality version of Beigel's nonspeedup theorem
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Control structures in hypothesis spaces: The influence on learning

This page was built for publication: Index Sets and Universal Numberings