Decision problem

Mathematical statement

A decision problem is an input set X with a yes-instance set Y⊆X, equivalently a proposition-valued specification P:X→Prop. Relative to an explicit computational model, a decider D must terminate on every x∈X and satisfy D(x)=true exactly when x∈Y.

Representative formula (exact TeX)

D:X\to B

Assumptions

• The input set X and yes-instance set Y are fixed, with Y⊆X.
• A decidability claim also requires an effective input representation and computational model; a finite lookup table establishes decidability only for that finite X.

Symbol scope

• D — candidate decider
• X — legal input set
• B — Boolean answer set

Intuition, definition, and misconceptions

Separate the specification from its implementation: Y or P describes correct answers, while D is a candidate procedure. It is a decider only if it terminates and agrees with the specification on every input.

For an explicit finite X, a complete table can exhaustively check D. Agreement on samples does not establish agreement over the entire domain; outside-domain inputs are not part of the current problem.

General infinite input domains require effective encodings and a computational model. This finite slice infers neither general computability nor undecidability from lookup tables.

A semidecision procedure that recognizes only yes-instances is not automatically a total decider, and finite test success does not decide a general infinite problem.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Set — Input domains and yes-instances are represented by sets.
• Proposition — The specification P(x) is a proposition depending on the input.
• Function mapping — A total decider gives one Boolean output for each legal input.

Verification boundary

A finite input table permits complete specification/output comparison; no general decidability is asserted without a computational model.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Construct explicit semantic bridges among Prop specifications, Bool deciders, effective representations and abstract computational models.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.