Statements (21)
Predicate | Object |
---|---|
gptkbp:instanceOf |
theoretical computer science
|
gptkbp:category |
gptkb:mathematical_concept
|
gptkbp:field |
gptkb:logic
computability theory |
https://www.w3.org/2000/01/rdf-schema#label |
Post's problem
|
gptkbp:importantFor |
major open problem in computability theory (until solved)
|
gptkbp:namedAfter |
gptkb:Emil_Post
|
gptkbp:relatedTo |
halting problem
Turing degree intermediate degree recursively enumerable set |
gptkbp:solutionYear |
1956
|
gptkbp:solvedBy |
gptkb:Andrey_Muchnik
gptkb:Richard_Friedberg |
gptkbp:status |
solved
|
gptkbp:type |
Are there recursively enumerable degrees between computable sets and the halting problem?
|
gptkbp:yearProposed |
1944
|
gptkbp:bfsParent |
gptkb:Recursively_enumerable_sets_of_positive_integers_and_their_decision_problems_(1944)
gptkb:Sacks_jump_inversion_theorem gptkb:Degrees_of_Unsolvability |
gptkbp:bfsLayer |
7
|