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

<p>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).</p>

<p>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$. </p>

<p>One can define a partial order over naming systems of a set $M$. $\gamma \leq \gamma&#39;$ iff some computable function can translate $\gamma$-names of objects in $M$ to $\gamma&#39;$-names of them.</p>

<p>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&#39;$ be defined by adding a bit to the names telling if the corresponding TM halts. Then $\gamma&#39;$-names can be translated to $\gamma$-names by a computable function but not vice versa. $\gamma&#39;$-names contain more information. If fact, we we can solve the halting problem for Turing machines if we use $\gamma&#39;$ as our encoding.</p>

<p>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.)</p>

<p>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.</p>

<p>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.</p>

<p>For further information:</p>

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

CC BY-SA 3.0
2011-04-26T08:57:31.610Z
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?
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-04-26T09:03:48.933Z
@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).
Kaveh
CC BY-SA 3.0
2011-04-26T13:46:32.763Z
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.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-04-27T06:01:40.747Z
As I said, universality does not care about the complexity issues like being exponentially slower.
Kaveh
CC BY-SA 3.0
2011-04-27T14:05:35.883Z
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?
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-04-27T15:10:28.540Z
You can design artificial models of computation that cannot work with binary numbers so if they are given a binary string they cannot do anything: e.g. Turing Machine where transition function is only allowed to use a fixed charter, say 0, of the input alphabet. But they will be artificial because any reasonable model should be able to convert encodings (although this might take a large time complexity).
Kaveh
CC BY-SA 3.0
2011-04-26T02:01:31.540Z
2011-04-26T04:07:03.037Z
2011-04-26T04:07:03.037Z
Kaveh
<p>Some models of computation are universal in the sense they can compute any arbitrary computable function $f:\mathbb{N} \rightarrow \mathbb{N}$.</p>

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

<ul>
<li>What are the names for these two types of universality?</li>
<li>Is there any further relevant distinction to be made?</li>
</ul>

<p>If I understand correctly, there are proofs of universality of systems, such as the <a href="http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine" rel="nofollow">Wolfram's 2-state 3-symbol Turing machine</a> which are controversial because of subtleties regarding enconding.</p>

CC BY-SA 3.0
2011-04-25T23:49:28.727Z
My understanding is that the controversiality of the universality proof for the Wolfram TM has specifically to do with the non-finiteness of the initial conditions for the TM - in the terminology of your question, that the set $A$ used for that proof is (essentially) the set $\mathbb{R}$ of reals (or if you prefer, functions from $\mathbb{N}\rightarrow\mathbb{N}$).  I suspect there would be substantially less controversy if the set $A$ were countable; effectively this corresponds to finitary input.
Steven Stadnicki
CC BY-SA 3.0
2011-04-26T00:57:25.740Z
With infinitary input, you can pull so many shenanigans in your functions $e$ and $d$ that it's not clear that the definition carries any real meaning.
Steven Stadnicki
CC BY-SA 3.0
2011-04-26T01:17:55.870Z
related: http://cstheory.stackexchange.com/questions/2537/is-there-a-non-turing-complete-model-of-computation-whose-halting-problem-is-unde
Kaveh
CC BY-SA 3.0
2011-04-26T03:47:01.753Z
ps: regarding your last line, I am not sure if discussing "Wolfram's 2-state 3-symbol Turing machine" is on-topic here, WP is good. But AFAIR it is not about encoding in the sense that you have mentioned. (Part of the controversy was also about the fact that Wolfram made the announcement by himself without waiting for the committee (which includes several famous experts on the topic) to verify the claim, check the FOM mailing list posts). Also take a look at my answer to the question I have linked above. I will try to answer questions below.
Kaveh
CC BY-SA 3.0
2011-04-26T08:59:18.223Z
What do you mean by WP?
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-04-27T06:00:43.133Z
WP=Wikipedia :)
Kaveh
<reference-request><computability><turing-machines><terminology><universal-computation>
Terminology for types of universal computation
Antonio Valerio Miceli-Barone
# Terminology for types of universal computation

(Asked by: username_0 on 2011-04-25)

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](http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine) which are controversial because of subtleties regarding enconding.

**Tags:** reference-request, computability, turing-machines, terminology, universal-computation

> **Comments:**
> **username_1**: My understanding is that the controversiality of the universality proof for the Wolfram TM has specifically to do with the non-finiteness of the initial conditions for the TM - in the terminology of your question, that the set $A$ used for that proof is (essentially) the set $\mathbb{R}$ of reals (or if you prefer, functions from $\mathbb{N}\rightarrow\mathbb{N}$).  I suspect there would be substantially less controversy if the set $A$ were countable; effectively this corresponds to finitary input.  
> **username_1**: With infinitary input, you can pull so many shenanigans in your functions $e$ and $d$ that it's not clear that the definition carries any real meaning.  
> **username_2**: related: http://cstheory.stackexchange.com/questions/2537/is-there-a-non-turing-complete-model-of-computation-whose-halting-problem-is-unde  
> **username_2**: ps: regarding your last line, I am not sure if discussing "Wolfram's 2-state 3-symbol Turing machine" is on-topic here, WP is good. But AFAIR it is not about encoding in the sense that you have mentioned. (Part of the controversy was also about the fact that Wolfram made the announcement by himself without waiting for the committee (which includes several famous experts on the topic) to verify the claim, check the FOM mailing list posts). Also take a look at my answer to the question I have linked above. I will try to answer questions below.  
> **username_0**: What do you mean by WP?  
> **username_2**: WP=Wikipedia :)  

---

## 1 answers

### Answer by username_2 on 2011-04-26. Score: 4 | Accepted answer

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:**
> **username_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?  
> **username_2**: @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).  
> **username_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.  
> **username_2**: As I said, universality does not care about the complexity issues like being exponentially slower.  
> **username_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?  
> **username_2**: You can design artificial models of computation that cannot work with binary numbers so if they are given a binary string they cannot do anything: e.g. Turing Machine where transition function is only allowed to use a fixed charter, say 0, of the input alphabet. But they will be artificial because any reasonable model should be able to convert encodings (although this might take a large time complexity).  

---

