In computability theory the **utm theorem (****universal turing machine theorem**), is a basic result about Gödel numberings of the set of computable functions. It proves the existence of a computable **universal function** which is capable of calculating any other computable function. The universal function is an abstract version of the universal turing machine, thus the name of the theorem.

According to the Church-Turing thesis,** computable functions** are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that any function which has an algorithm is computable.

### UTM theorem

Let be a Gödel numbering of the set of computable functions, then the partial function

defined as

is computable.

is called the **universal function** for

There are many equivalent ways to define the class of computable functions. For concreteness, the remainder of this article will assume that **computable functions** have been defined as those finitary partial functions on the natural numbers that can be calculated by a Turing machine. There are many equivalent models of computation that define the same class of computable functions. These models of computation include

**Turing machines, μ-recursive functions, Lambda calculus, Post machines**(**Post-Turing machines**and**tag machines**),**Register machines**

and others.

Each computable function *f* takes a fixed number of natural numbers as arguments. Because the functions are partial, they may not be defined for every possible choice of input. If a computable function is defined then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function). These functions are also called **partial recursive functions**. In computability theory, the **domain** of a function is taken to be the set of all inputs for which the function is defined.

A function which is defined for all arguments is called **total**. If a computable function is total, it is called a **total computable function** or **total recursive function**.

The notation indicates that the partial function *f* is defined on arguments , and the notation indicates that *f* is defined on the arguments and the value returned is *y*.

### Applying the UTM Theorem for Symbolic Analysis

Symbolic Analysis is defined using GrammarWare, ModelWare, SimulationWare and KnowledgeWare.

Hence, the command-predicate of the Atomistic Hybrid Object (AHO) – *which corresponds symbol in the architecture* – is the

**universal function**for the symbol. It has been defined as a

*in the semantics of the Symbolic language. Hence, we use as our model of computation Prolog and the inference engine inside it:*

**clause**For each Java grammar term or C++ term there is a clause type and a subtype in the Symbolic language. It is then the specification for SimulationWare considering that original grammar term.

Some links:

- Rogers, H. (1987) [1967].
*The Theory of Recursive Functions and Effective Computability*. First MIT press paperback edition. ISBN 0-262-68052-1. - Soare, R. (1987).
*Recursively enumerable sets and degrees*. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-15299-7.

## Leave a comment

Comments feed for this article