The intrinsic difficulty of recursive functions
Studia Logica 56 (3):427 - 454 (1996)
| Abstract | This paper deals with a philosophical question that arises within the theory of computational complexity: how to understand the notion of INTRINSIC complexity or difficulty, as opposed to notions of difficulty that depend on the particular computational model used. The paper uses ideas from Blum's abstract approach to complexity theory to develop an extensional approach to this question. Among other things, it shows how such an approach gives detailed confirmation of the view that subrecursive hierarchies tend to rank functions in terms of their intrinsic, and not just their model-dependent, difficulty, and it shows how the approach allows us to model the idea that intrinsic difficulty is a fuzzy concept. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,664 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJulia Tanner (2007). Intrinsic Value and the Argument From Regress. Forum Philosophicum 12 (2):313-322..
Stanley S. Wainer (1999). Accessible Recursive Functions. Bulletin of Symbolic Logic 5 (3):367-388.
Dan Marshall (2009). Can 'Intrinsic' Be Defined Using Only Broadly Logical Notions? Philosophy and Phenomenological Research 78 (3):646-672.
Arto Salomaa (1985). Computation and Automata. Cambridge University Press.
T. L. S. Sprigge (1984). Non-Human Rights: An Idealist Perspective. Inquiry 27 (1-4):439 – 461.
V. Hoffmann-Kolss (2010). Denby on the Distinction Between Intrinsic and Extrinsic Properties. Mind 119 (475):763-772.
Stephen E. Newstead, Peter Bradon, Simon J. Handley, Ian Dennis & Jonathan St B. T. Evans (2006). Predicting the Difficulty of Complex Logical Reasoning Problems. Thinking and Reasoning 12 (1):62 – 90.
Bruce Edmonds (2000). Complexity and Scientific Modelling. Foundations of Science 5 (3):379-390.
Sanjay Jain & Arun Sharma (1997). The Structure of Intrinsic Complexity of Learning. Journal of Symbolic Logic 62 (4):1187-1201.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads3 ( #201,730 of 548,999 )Recent downloads (6 months)1 ( #63,327 of 548,999 )How can I increase my downloads? |
My notes
Discussion
