Keyboard graph navigation: press N for concepts or E for relations; use arrow keys, Home, and End to move; Enter selects; Shift plus Enter selects and centers; plus and minus zoom; zero fits; Escape clears the selection. Use the visible viewport buttons as alternatives to dragging, wheel, and pinch gestures.
Canonical static concept record
Open this concept in the interactive graphRead the Markdown equivalent
A partial function computed by some Turing machine; a total computable function halts on every input in its domain type.
wp-computable-functionnlab-computable-functionturing-computable-numbersEach relation below ends at this concept.
This is an authored directed relation from the source endpoint to the target endpoint.
A terminating or partial algorithm determines a partial function. The assertion that every effective algorithm is captured by Turing computability is the Church–Turing thesis, not a formal theorem.
Reinterpret an object, pass to an equivalent presentation, or relate canonically corresponding structures; the carrier may change.
turing-computable-numbersThis is an authored directed relation from the source endpoint to the target endpoint.
Each deterministic Turing machine induces a partial function by its input-output behavior; machines that halt on every input compute total functions.
Apply a standard functorial or canonical construction whose output is not merely a reduct of the input and is not generally an equivalent presentation of the same object.
turing-computable-numbersEach relation below starts at this concept.
This is an authored directed relation from the source endpoint to the target endpoint.
The reduction is the computable map whose membership-preservation equivalence transfers decidability and many undecidability arguments from the target problem to the source problem.
A mathematical concept supplies part of the formal language, state space, representation, or analytic machinery used by a scientific or mathematical-physics concept. The source is the mathematical predecessor; this does not claim that physical content follows from mathematics alone.
openlogic-computability