in set theory. See also Karp reduction Notes References M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. . S. C. Kleene, 1952. Introduction to Metamathematics. Amsterdam: North-Holland. S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics v. 2 n. 59, 379–407. A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965. H. Rogers, 1967. Theory of recursive functions and effective computability. McGraw-Hill. R. Soare, 1987. Recursively enumerable sets and degrees, Springer. External links NIST Dictionary of Algorithms and Data Structures: Turing reduction University of Cambridge, Andrew Pitts, Tobias Kohn: Computation Theory Prof. Jean Gallier’s Homepage Reduction (complexity) Alan Turing he:רדוקציה חישובית