An algorithm specifies effective steps; a decision procedure must terminate on every permitted input.
Key knowledge
An algorithm specifies computable steps for obtaining a result. A decision procedure for a yes-or-no problem must return the correct answer and terminate for every input in its declared domain.
Conditions and scope
Specify input representation, permitted operations and the required result.
A procedure that may run forever on some inputs is not a total decision procedure for that problem.
Sources · 4
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Effective steps and total decision-procedure requirements.
2026-10-10 · Compared the dictionary definition with Cambridge's decision-problem specification.
Foundational review
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Sources from other places
Scope or convention differs
A computational method maps declared inputs to outputs, illustrated by a finite-list procedure.
This practical course does not independently formalise every total decision-procedure condition.
University of Helsinki, Department of Computer Science
There is no algorithm that always terminates and correctly decides, for every program-input pair in a Turing-complete computation model, whether that program eventually halts on that input.
For nonnegative cost functions, T(n)=O(g(n)) means there are constants c>0 and n₀ such that T(n)≤cg(n) for every n≥n₀. A time or space complexity bound must specify the computation model, input-size measure and case being analysed.
A DFA consists of finite states Q, finite alphabet Σ, total transition δ:Q×Σ→Q, start q₀ and accepting states F. It reads a finite string once, accepts when the final state lies in F and recognizes a regular language.
On a sorted random-access array, compare the target with the middle key and discard the half that cannot contain it; repeat until a matching key is found or the remaining interval is empty. Every step preserves all possible matches within the interval and halves its size.
To maximize the number of compatible intervals, repeatedly take the available interval finishing earliest and discard overlapping intervals. Replacing an optimum's first interval by this choice cannot reduce the feasible remainder, giving the exchange proof. Sorting by finish time yields O(n log n) time.
In a connected undirected weighted graph, if a set of chosen edges lies within some minimum spanning tree and a cut crosses none of them, a lightest edge crossing that cut can be added while preserving this invariant. Equal-weight choices need not occur in every optimum.