Definitions

Machine

A machine is something that can execute a certain language, namely its machine language. It executes operations at a certain speed (which may be measured in virtual units).

Examples:

• A processor. Its machine language is its instruction set.
• The Java Virtual Machine. Its machine language "is" Jasmin.
• An idealized car. Its machine language is turning the wheel, changing gears, ...
• A method. Its machine language are allowed arguments.

Language

A language can be represented as a set of strings. Each of these strings has a meaning, and could be called a text, or a program. The set of meanings expressible in a language is the expressive power of the language.

Examples:

• see examples for "Machine"
• English as understood by some English speaker X
• Scala

Procedure

A procedure is an implementation of a function. It is often simply called a (pure) function by programmers. But the term procedure specifically refers to an implementation of a function, while the term function simply refers to a specification.

Note that a procedure always defines a function (potentially partial, depending on the context), even though it may not always be clear which function.

Note also that a procedure is a special type of machine, namely a stateless one.

Expressive Power of a Function (or, by abuse of notation, of a Procedure (and, by abuse of abuse of notation, of a Machine))

In the following, we assume without loss of generality that the input and output types of the functions are sigma* languages, where sigma is a finite alphabet, and * is the kleene star.

Given a set C of allowed representation functions, the expressive power of a partial function f with respect to C is the set S of all partial functions it can represent, or more precisely:

S is the set of all s such that there exists c (depending on s) in C such that for all x in the domain of s, f(c(x)) = s(x).

In the following, let a trivial encoding from a language A* to a language B* be any function t such that it can be computed by a sequential application of a function h from A to B* on each letter of an element of A* (i.e. t simply is a homomorphism between the free monoids A* and B*).

The default set C of allowed representation functions shall be the set of functions that embed a trivial encoding of their input into a constant string. Any other C will typically be a superset of the default set C.

If we talk about the expressive power of f without mentioning a set C of allowed representation functions, we will implicitly mean it to be with respect to the default set C.

We shall say in particular that a function f is Turing-complete if the expressive power of f contains a partial function that maps expressions to values in a Turing-complete language (this is equivalent to saying that S contains all such functions).