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 yes-or-no problem represented by a set of finite inputs whose membership is to be decided.
wp-decision-problemturing-computable-numbersEach relation below ends at this concept.
No direct relations are authored in this direction.
Each relation below starts at this concept.
This is an authored directed relation from the source endpoint to the target endpoint.
A decision problem is decidable when some algorithm halts with the correct answer on every input.
The target is a member or subtype of the broader source class.
turing-computable-numbersThis is an authored directed relation from the source endpoint to the target endpoint.
A many-one reduction supplies a total computable translation of instances so that one answer to the target decision problem decides the original instance without adaptive oracle queries.
Equip an existing carrier or structured object with additional chosen data, when such compatible data exists. Use a construction junction when several independently meaningful inputs must coexist on the same carrier or interact compatibly.
openlogic-computabilityThis is an authored directed relation from the source endpoint to the target endpoint.
An undecidable problem is a decision problem for which no total algorithm returns the correct yes-or-no answer on every encoded instance.
The target is a member or subtype of the broader source class.
turing-computable-numbers