This is a rigourous definition of an algorithm using set theory.
computational method := A quadruple, (Q, I, Ω, f)
in which Q is a set containing
subsets I and Ω. And f is a function Q → Q. f should leave Ω pointwise fixed (f(q) = q∀q ∈ Ω)
computational method :~ the quadruple (Q, I, Ω, f) is intended to represent respectively the states of the computation (Q), the input (I), the output(Ω), and the computational rule (f).
$$ \color{default}\left( \color{c1} Q \color{default}, \color{c2}I \color{default}, \color{c3}\Omega \color{default}, \color{c4}f \color{default}\right) $$
pointwise fixe := f(q) should equal q for all q ∈ Ω
Each x ∈ I defines a computational sequence, x0, x1, x2, …, with x0 = x and f(xk) = xk + 1 for k ≥ 0
A computational sequence is said to terminate in k steps if k is the smallest integer for which xk is in Ω, and is said to produce output xk from x (Recall the pointwise property of Ω)
If ∀x ∈ I the computational method terminates, then it is an algorithm.
We essentially turn the states of the algorithm (blocks in the flowchart) to be words, and we want the words to be as short as possible. If we wish to restrict the notation of algorithm so that only elementary operations are involved, we can place restrictions on the quadruple of the computational method, Q, I, Ω and f, for example as follows:
Let A be a finite set of letters, and let A* be the set of all strings on A, or A* is words. (i.e., the set of all ordered sequences x1x2…xn, where n ≥ 0 and xj is in A for 1 ≤ j ≤ n). The idea is to encode the states of the computation, Q, so that they are represented by strings of A*. Now let N be a nonnegative integer and let Q be the set of all (σ, j), where σ ∈ A* and j is an integer, 0 ≤ j ≤ N; Let I be the subset of Q with j = 0 (j = 0 represents that this is the starting state) and let Ω be the subset with j = N which shows the ending state. If θ and σ are strings in A*, we say that θ occurs in σ if σ has the form αθω for strings α and ω. To reiterate, σ = αθω. To complete our definition, let f be a function of the following type, defined by the strings θj, ϕj and the integers aj, bj for 0 ≤ j ≤ N:
f(σ, j) = (σ, aj) if θj does not occur in σ; :~ you carry the state of computation to another step number.
f(σ, j) = (αϕω, bj) if α is the shortest possible string for which σ = αθjω; θj does occur in σ
f(σ, N) = (σ, N) ““”
We need the states of computation to be ordered.
[[the_euclidean_algorithm___11_06_2022__090230167#rigour]] TODO
tags taocp