Algorithm

Builds on Turing machine Model of computation

Definition

Let $I$ and $O$ be sets of finite objects, the inputs and the outputs, encoded as strings over a finite alphabet. An algorithm from $I$ to $O$ is a finite description of a procedure with these properties:

at each stage the procedure performs one elementary step, which is uniquely determined by the description and the current data;
for each input $x \in I$ the procedure stops after finitely many steps;
when it stops on input $x$ , it outputs an element $f(x) \in O$ .

The algorithm then computes the function $f \colon I \to O$ . In a fixed model of computation this is made exact: an algorithm is, for example, a Turing machine that halts on every input in $I$ .

Remarks

The informal clauses and the formal model are linked by the Church–Turing thesis, which is a thesis and not a theorem. It says that every function computable by an informal algorithm is computable by a Turing machine. Many texts drop clause 2 and call a procedure that may run forever a partial algorithm or a semi-algorithm. Randomized and nondeterministic algorithms relax clause 1.

Example: the Euclidean algorithm is an algorithm from pairs of natural numbers to natural numbers. Each step replaces $(a, b)$ by $(b, a \bmod b)$ , the second entry strictly decreases while it is positive, so the procedure stops, and it outputs $\gcd(a, b)$ .

Non-example: "search the natural numbers $n = 1, 2, 3, \dots$ for an odd perfect number and output the first one found" is a precise procedure. But nobody knows whether it stops, so it is not known to satisfy clause 2.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Model of computation concept
Turing machine concept
Algorithm definition

Where this leads

1 page builds on this one.

Neighbor joining

Tag	`5K1F0ZSN51`
URI	`m2://5K1F0ZSN51`
Kind	definition
Writing	W0 stub
MSC	68W01, 68Q10
Defines	Algorithm
Uses	Turing machine, Model of computation
Changed	3 November 2026

Algorithm

Definition

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by