Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra

Annals of Pure and Applied Logic 163 (8):1108-1139 (2012)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2011.12.030

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,283

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Computability and Complexity: From a Programming Perspective Vol. 21.N. D. Jones - 1997 - MIT Press.
Handbook of computability theory.Edward R. Griffor (ed.) - 1999 - New York: Elsevier.
Compressibility and Kolmogorov Complexity.Stephen Binns & Marie Nicholson - 2013 - Notre Dame Journal of Formal Logic 54 (1):105-123.
Computability in Context: Computation and Logic in the Real World.S. B. Cooper & Andrea Sorbi (eds.) - 2011 - World Scientific.
Computability, an introduction to recursive function theory.Nigel Cutland - 1980 - New York: Cambridge University Press.
Decidable discrete linear orders.M. Moses - 1988 - Journal of Symbolic Logic 53 (2):531-539.
Computable and continuous partial homomorphisms on metric partial algebras.Viggo Stoltenberg-Hansen & John V. Tucker - 2003 - Bulletin of Symbolic Logic 9 (3):299-334.
Domains for computation in mathematics, physics and exact real arithmetic.Abbas Edalat - 1997 - Bulletin of Symbolic Logic 3 (4):401-452.
Introduction to Computability Theory.D. Normann - 2010
Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
Hyperloops do not threaten the notion of an effective procedure.Tim Button - 2009 - Lecture Notes in Computer Science 5635:68-78.
Effective complexity as a measure of information content.James W. McAllister - 2003 - Philosophy of Science 70 (2):302-307.
Why Solovay real produces Cohen real.Janusz Pawlikowski - 1986 - Journal of Symbolic Logic 51 (4):957-968.

Analytics

Added to PP
2013-10-27

Downloads
40 (#400,484)

6 months
13 (#200,551)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Inside the Muchnik degrees I: Discontinuity, learnability and constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.

Add more citations

References found in this work

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Recursion-theoretic hierarchies.Peter G. Hinman - 1978 - New York: Springer Verlag.
Descriptive Set Theory.Richard Mansfield - 1981 - Journal of Symbolic Logic 46 (4):874-876.
Closed choice and a uniform low basis theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.

View all 13 references / Add more references