Theoretical Computer Science

Terminology for types of universal computation

Some models of computation are universal in the sense they can compute any arbitrary computable function $f:\mathbb{N} \rightarrow \mathbb{N}$.

Other models are universal only as far as the input and output are encoded:
$\exists$ a set $A$ such that $\forall$ computable functions $f:\mathbb{N} \rightarrow \mathbb{N}$ the model can compute a function $f':A \rightarrow A$, such that $\forall n \in \mathbb{N},\ f(n)\ = \ d(f'(e(n)))$, for some encoding and decoding functions:
$e:\mathbb{N} \rightarrow A$
$d:A \rightarrow \mathbb{N}$
with suitable constraints on the computability (and possibly the complexity) of these functions.

  • What are the names for these two types of universality?
  • Is there any further relevant distinction to be made?

If I understand correctly, there are proofs of universality of systems, such as the Wolfram's 2-state 3-symbol Turing machine which are controversial because of subtleties regarding enconding.


The key words you should search for are "naming systems", "representation", "notation", "numbering", ...

The usual concepts of computability are defined over strings (either unary which is usually stated as $\mathbb{N}$ or binary which is state as computability over $\Sigma^*$ where $\Sigma = \{ 0,1 \} $). (They can be extended to $\Sigma^\omega$ but here I will stick to the countable case.) A model of computation is called universal if it is Turing-complete (i.e. it can compute any Turing computable function).

If we want to talk about computability over other sets, then we need a naming system. A naming system for $M$ is a partial function from $\Sigma^*$ onto $M$. If we have two sets $Y$ and $M$, and a naming system for each of them, then we can talk about computability of functions from $Y$ to $M$.

One can define a partial order over naming systems of a set $M$. $\gamma \leq \gamma'$ iff some computable function can translate $\gamma$-names of objects in $M$ to $\gamma'$-names of them.

Let me give a simple example. Assume that $M$ is the set of Turing machines, and $\gamma$ is one of the common ways of encoding Turing machines as explained in computability/complexity books. Let $\gamma'$ be defined by adding a bit to the names telling if the corresponding TM halts. Then $\gamma'$-names can be translated to $\gamma$-names by a computable function but not vice versa. $\gamma'$-names contain more information. If fact, we we can solve the halting problem for Turing machines if we use $\gamma'$ as our encoding.

Obviously we don't want to have non-computable information coded inside the names of objects as above, so we use names which have the least amount of information in computability (assuming that they exist). (In complexity, the complexity of a problem can depend on the naming system that is used for the inputs, and different naming systems can be more suitable for different purposes. There is no least if we change the requirement for translation from being computable to say poly-time computable as is shown by padding arguments.)

After defining the computability over other sets using naming systems, one can talk about a universal model of computation over them w.r.t. fixed naming systems.

Now, if the names in a naming system contain non-trivial information, then it is not very interesting for a machine to be universal w.r.t. that naming system anymore.

For further information:

  • Yuri L. Ershov, Sergei S. Goncharov, Anil Nerode, "Handbook of Recursive Mathematics", vol I and II, 1998
  • Klaus Weihrauch, "Computable Analysis", 2000

Comments (5)

  • +0 – Thanks. I'm interested in particular to the distinction between models that are universal respect to unary and binary encodings of the natural numbers. Are there models that are universal only respect to an unary encoding or this universality also implies universality respect to a binary encoding? — Apr 26, 2011 at 08:57  
  • +1 – @Antonio, they are the same from the computability point of view (AFAIK). You can easily convert from unary encoding to binary and vice versa. But in computer science people usually prefer binary because of complexity issues (converting binary to unary takes exponential time). In computability theory, specially math/recursion theory oriented books, people usually prefer unary since mathematicians are more familiar with natural numbers generated by $0$ and the successor operator than with empty string and operations over them (and they are not concerned about complexity but only computability). — Apr 26, 2011 at 09:03  
  • +0 – Ok. I wanted to know if there are models which are universal only respect to unary encodings and hence are exponentially slower than models which operate on binary encodings. — Apr 26, 2011 at 13:46  
  • +0 – As I said, universality does not care about the complexity issues like being exponentially slower. — Apr 27, 2011 at 06:01  
  • +0 – I mean, does there exist a model that computes arbitrary computable functions only if the input and output are encoded in unary form, but not if they are encoded in binary form? — Apr 27, 2011 at 14:05  

External Links

External links referenced by this document: