DOI: 10.4324/9780415249126-Y006-1

Version: v1, Published online: 1998

Retrieved May 22, 2024, from https://www.rep.routledge.com/articles/thematic/turing-reducibility-and-turing-degrees/v-1

Version: v1, Published online: 1998

Retrieved May 22, 2024, from https://www.rep.routledge.com/articles/thematic/turing-reducibility-and-turing-degrees/v-1

## Article Summary

A reducibility is a relation of comparative computational complexity (which can be made precise in various non-equivalent ways) between mathematical objects of appropriate sorts. Much of recursion theory concerns such relations, initially between sets of natural numbers (in so-called classical recursion theory), but later between sets of other sorts (in so-called generalized recursion theory). This article considers only the classical setting. Also Turing first defined such a relation, now called Turing- (or just T-) reducibility; probably most logicians regard it as the most important such relation. Turing- (or T-) degrees are the units of computational complexity when comparative complexity is taken to be T-reducibility.

Citing this article:

Hodes, Harold. Turing reducibility and Turing degrees, 1998, doi:10.4324/9780415249126-Y006-1. Routledge Encyclopedia of Philosophy, Taylor and Francis, https://www.rep.routledge.com/articles/thematic/turing-reducibility-and-turing-degrees/v-1.

Copyright © 1998-2024 Routledge.

Hodes, Harold. Turing reducibility and Turing degrees, 1998, doi:10.4324/9780415249126-Y006-1. Routledge Encyclopedia of Philosophy, Taylor and Francis, https://www.rep.routledge.com/articles/thematic/turing-reducibility-and-turing-degrees/v-1.

Copyright © 1998-2024 Routledge.