A structured visual guide to the major mathematical areas and their relationships.
Search by code, branch, topic, subtopic, or a keyword from the descriptions.
This subtopic covers computability and recursion theory, focusing on what can be computed, how efficiently, and with what formal limitations. It is used to classify algorithms and problems by computability and complexity, and to understand undecidability phenomena. Applications include theoretical computer science, cryptography, automated reasoning, and the design of algorithms under provable resource constraints.
This topic covers automata and formal grammars, including finite-state machines, pushdown automata, and the grammar formalisms that generate regular and context-free languages. It is the bridge between formal language theory and computability.
Used to analyse languages, specify parsers, and provide the first rigorous layer of formal computation theory.
This topic covers Turing machines and related notions such as variants of effective procedures, encodings, and computable operations. It is the standard model of algorithmic computation in recursion theory.
Used to formalize the notion of algorithm, prove undecidability, and establish the limits of effective computation.
This topic covers complexity of computation, including time, space, and resource-bounded classes of problems. It asks not just whether problems are computable but how efficiently they can be solved.
Computational complexity theory (Wikipedia)
Used to classify problems by inherent difficulty and to compare the feasibility of algorithms under explicit resource constraints.
This topic covers recursive functions and relations, which are the function and relation analogues of effective computability. They form a core language for defining algorithmic classes and proving closure properties.
Recursive function (Wikipedia)
Used to specify computable functions precisely and to prove metatheorems about what operations preserve computability.
This topic covers recursively enumerable sets and degrees, describing the relative algorithmic content of sets and the partial ordering induced by Turing reducibility. It is a central classification tool in recursion theory.
Used to compare the noncomputable content of sets and to organise hierarchies of unsolvability.
This topic covers algorithmic randomness and dimension, which study the effective incompressibility of sequences and the fine structure of randomness. It connects computation with probability and information theory.
Algorithmic randomness (Wikipedia)
Used to measure algorithmic unpredictability and to refine the notion of randomness beyond classical probability.
This topic covers undecidability and degrees of sets of sentences, asking how hard it is to decide membership or truth for logical theories and sentence sets. It is a fundamental bridge between logic and computation.
Used to prove that a theory cannot be decided algorithmically and to compare the hardness of logical decision problems.
This topic covers word problems and related decision problems, especially in algebraic structures and formal systems. It studies whether a finite presentation yields an effective method for determining equality or equivalence.
Word problem (mathematics) (Wikipedia)
Used to classify finitely presented structures by solvability of their word problems.
This topic covers hierarchies in recursion theory, such as arithmetical and analytical hierarchies, that stratify definability and complexity. It helps locate problems within a graded structure of logical strength.
Analytical hierarchy (Wikipedia)
Used to compare the logical strength of definitional schemes and to classify problems by alternation depth.
This topic covers applications of computability and recursion theory across mathematics and allied fields. It highlights how recursion-theoretic methods can clarify algebraic, combinatorial, and analytic problems.
Computability theory (Wikipedia)
Used when computability methods are applied beyond pure recursion theory to solve or classify concrete mathematical problems.