Access to the full content is only available to members of institutions that have purchased access. If you belong to such an institution, please log in or find out more about how to order.



Recursion-theoretic hierarchies

DOI: 10.4324/9780415249126-Y076-1
Version: v1,  Published online: 1998
Retrieved November 30, 2022, from

Article Summary

In mathematics, a hierarchy is a ‘bottom up’ system classifying entities of some particular sort, a system defined inductively, starting with a ‘basic’ class of such entities, with further (‘higher’) classes of such entities defined in terms of previously defined (‘lower’) classes. Such a classification reflects complexity in some respect, one entity being less complex than another if it appears ‘earlier’ (‘lower’) then that other. Many of the hierarchies studied by logicians construe complexity as complexity of definition, placing such hierarchies within the purview of model theory; but even such notions of complexity are closely tied to species of computational complexity, placing them also in the purview of recursion theory.

Citing this article:
Hodes, Harold. Recursion-theoretic hierarchies, 1998, doi:10.4324/9780415249126-Y076-1. Routledge Encyclopedia of Philosophy, Taylor and Francis,
Copyright © 1998-2022 Routledge.

Related Searches