DOI: 10.4324/9780415249126-Y076-1
Version: v1, Published online: 1998
Retrieved March 29, 2024, from https://www.rep.routledge.com/articles/thematic/recursion-theoretic-hierarchies/v-1
Version: v1, Published online: 1998
Retrieved March 29, 2024, from https://www.rep.routledge.com/articles/thematic/recursion-theoretic-hierarchies/v-1
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, https://www.rep.routledge.com/articles/thematic/recursion-theoretic-hierarchies/v-1.
Copyright © 1998-2024 Routledge.
Hodes, Harold. Recursion-theoretic hierarchies, 1998, doi:10.4324/9780415249126-Y076-1. Routledge Encyclopedia of Philosophy, Taylor and Francis, https://www.rep.routledge.com/articles/thematic/recursion-theoretic-hierarchies/v-1.
Copyright © 1998-2024 Routledge.