The intrinsic difficulty of recursive functions

Studia Logica 56 (3):427 - 454 (1996)
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 (categorize this paper)
DOI 10.1007/BF00372775
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 16,667
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Stewart Shapiro (1981). Understanding Church's Thesis. Journal of Philosophical Logic 10 (3):353--65.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

10 ( #235,035 of 1,726,249 )

Recent downloads (6 months)

5 ( #147,227 of 1,726,249 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.