Concepedia

Post's Problem

Post's Problem is a fundamental question in recursion theory that asks whether there exists a recursively enumerable set whose Turing degree is strictly intermediate between the computable sets and the halting problem.

29

Publications

1.5K

Citations

38

Authors

26

Institutions

Publications per year

2017–2026

1

Parents

Publications

29

Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines

Marvin Minsky · Annals of Mathematics · 1961 · 710 citations

, , +16

The Word Problem in Semi-Groups With Cancellation

Alan Turing · Annals of Mathematics · 1950 · 76 citations

, , +15

ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS

Julien Cassaigne, Tero Harju, Juhani Karhumäki · International Journal of Algebra and Computation · 1999 · 71 citations

, , +13

Strong reducibilities

Piergiorgio Odifreddi · Bulletin of the American Mathematical Society · 1981 · 63 citations · Full text

, , +11

Post’s problem, admissible ordinals, and regularity

Gerald E. Sacks · Transactions of the American Mathematical Society · 1966 · 56 citations · Full text

, , +13

1–5 of 29

Authors

38

  1. VH
    Vesa Halava

    University of Turku, Finland

    3 publications · 64 citations

    3

    h-index

  2. RI
    Robert I. Soare

    University of Chicago, United States

    3 publications · 98 citations

    3

    h-index

  3. WE
    W. E. Singletary

    Pennsylvania State University, United States

    3 publications · 37 citations

    3

    h-index

  4. GE
    Gerald E. Sacks

    Massachusetts Institute of Technology, United States

    3 publications · 94 citations

    3

    h-index

  5. TH
    Tero Harju

    University of Turku, Finland

    3 publications · 116 citations

    3

    h-index

1–5 of 38

Institutions

26

  1. University of Turku

    Turku, Finland

    3 h-index

    8 publications

    277 citations

  2. University of Illinois System

    Urbana, United States

    2 h-index

    2 publications

    24 citations

  3. TU Dortmund University

    Dortmund, Germany

    2 h-index

    2 publications

    45 citations

  4. Turku Centre for Computer Science

    Turku, Finland

    2 h-index

    4 publications

    90 citations

  5. University of Illinois Chicago

    Chicago, United States

    2 h-index

    2 publications

    45 citations

  6. University of California, Berkeley

    Berkeley, United States

    2 h-index

    3 publications

    122 citations

  7. University of Connecticut

    Storrs, United States

    2 h-index

    2 publications

    45 citations

  8. Beijing Institute of Radio Metrology and Measurement

    Beijing, China

    1 h-index

    3 publications

    30 citations

1–8 of 26

Venues

  1. Journal of Symbolic Logic

    6 publications · 158 citations

    6

    h-index

  2. Bulletin of the American Mathematical Society

    3 publications · 96 citations

    3

    h-index

  3. International Journal of Algebra and Computation

    IJAC · 2 publications · 84 citations

    2

    h-index

  4. Annals of Mathematics

    2 publications · 786 citations

    2

    h-index

  5. Transactions of the American Mathematical Society

    TRAN · 2 publications · 75 citations

    2

    h-index

1–5