Version: v1, Published online: 1998
Retrieved November 28, 2023, from https://www.rep.routledge.com/articles/thematic/turing-reducibility-and-turing-degrees/v-1
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.
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-2023 Routledge.