Concepedia

Turing Reducibility

Turing Reducibility is a binary relation between sets of natural numbers that specifies when one set can be decided by an algorithm using an oracle for another set, thereby defining the relative computability of the former in terms of the latter.

109

Publications

13.1K

Citations

140

Authors

100

Institutions

Publications per year

2017–2026

8

Variants

Turing Reduction

Parents

Publications

109

On Computable Numbers, with an Application to the Entscheidungsproblem

Alan Turing · Proceedings of the London Mathematical Society · 1937 · 8.1K citations

, , +10

On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction

Alan Turing · Proceedings of the London Mathematical Society · 1938 · 592 citations

, , +12

The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions

Calvin C. Elgot, Martin Davis · Mathematics of Computation · 1966 · 329 citations

, , +16

The Upper Semi-Lattice of Degrees of Recursive Unsolvability

S. C. Kleene, Emil L. Post · Annals of Mathematics · 1954 · 276 citations

, , +13

Fearful symmetry: Is God a geometer?

Choice Reviews Online · 1993 · 191 citations

, , +12

1–5 of 109

Authors

140

  1. FS
    Frank Stephan

    National University of Singapore, Singapore

    6 publications · 247 citations

    6

    h-index

  2. SG
    Stephen G. Simpson

    Pennsylvania State University, United States

    4 publications · 187 citations

    4

    h-index

  3. RA
    Richard A. Shore

    Cornell University, United States

    4 publications · 115 citations

    4

    h-index

  4. RB
    Richard Beigel

    Yale University, United States

    4 publications · 175 citations

    4

    h-index

  5. AN
    André Nies

    University of Auckland, New Zealand

    3 publications · 137 citations

    3

    h-index

1–5 of 140

Institutions

100

  1. University of Wisconsin–Madison

    Madison, United States

    6 h-index

    9 publications

    282 citations

  2. University of Chicago

    Chicago, United States

    6 h-index

    7 publications

    318 citations

  3. National University of Singapore

    Singapore, Singapore

    5 h-index

    6 publications

    193 citations

  4. Victoria University of Wellington

    Wellington, New Zealand

    5 h-index

    8 publications

    130 citations

  5. University of California, Berkeley

    Berkeley, United States

    5 h-index

    6 publications

    229 citations

  6. University of California San Diego

    San Diego, United States

    4 h-index

    4 publications

    156 citations

  7. University of Notre Dame

    Notre Dame, United States

    4 h-index

    6 publications

    282 citations

  8. Pennsylvania State University

    State College, United States

    4 h-index

    5 publications

    225 citations

1–8 of 100

Venues

  1. Journal of Symbolic Logic

    26 publications · 906 citations

    19

    h-index

  2. Theoretical Computer Science

    6 publications · 195 citations

    6

    h-index

  3. Transactions of the American Mathematical Society

    TRAN · 5 publications · 172 citations

    5

    h-index

  4. SIAM Journal on Computing

    4 publications · 166 citations

    4

    h-index

  5. Bulletin of Symbolic Logic

    3 publications · 101 citations

    3

    h-index

1–5