MSC2020 · 03Dxx

Computability and recursion theory

4 mapped entries · Browse and filter all →

Counts include all statuses and descendants. Classifications are editorial or inferred from community fields, not an AMS assessment of the problem.

Subcategories

03D03Thue and Post systems, etc.0 03D05Automata and formal grammars in connection with logical questions0 03D10Turing machines and related notions1 03D15Complexity of computation (including implicit computational complexity)0 03D20Recursive functions and relations, subrecursive hierarchies0 03D25Recursively (computably) enumerable sets and degrees0 03D28Other Turing degree structures0 03D30Other degrees and reducibilities in computability and recursion theory0 03D32Algorithmic randomness and dimension0 03D35Undecidability and degrees of sets of sentences0 03D40Word problems, etc. in computability and recursion theory0 03D45Theory of numerations, effectively presented structures0 03D50Recursive equivalence types of sets and structures, isols0 03D55Hierarchies of computability and definability0 03D60Computability and recursion theory on ordinals, admissible sets, etc.0 03D65Higher-type and set recursion theory0 03D70Inductive definability0 03D75Abstract and axiomatic computability and recursion theory0 03D78Computation over the reals, computable analysis0 03D80Applications of computability and recursion theory0 03D99Computability and recursion theory0

Mapped problems

OP-11934Dynamical systemsStatus unassessed

Turing universality in celestial mechanics

Turing universality in celestial mechanics. Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.

Universality in Computable Dynamical Systems — Old and New· Source question · editorial summary· 2025

OP-11933Dynamical systemsStatus unassessed

A dynamical operation characterizing Turing universality

A dynamical operation characterizing Turing universality. Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.

Universality in Computable Dynamical Systems — Old and New· Source question · editorial summary· 2025

OP-11932Dynamical systemsStatus unassessed

Topological invariants of computational complexity

Topological invariants of computational complexity. Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.

Universality in Computable Dynamical Systems — Old and New· Source question · editorial summary· 2025

OP-12016Logic and foundationsOpen