2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Commented Apr 25, 2011 at 23:49
  • $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Commented Apr 26, 2011 at 0:57
  • $\begingroup$ related: cstheory.stackexchange.com/questions/2537/… $\endgroup$
    – Kaveh
    Commented Apr 26, 2011 at 1:17
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Apr 26, 2011 at 3:47
  • $\begingroup$ What do you mean by WP? $\endgroup$
    – Antonio Valerio Miceli-Barone
    Commented Apr 26, 2011 at 8:59

1 Answer 1

Reset to default
4
$\begingroup$

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
Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Antonio Valerio Miceli-Barone
    Commented Apr 26, 2011 at 8:57
  • 1
    $\begingroup$ @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). $\endgroup$
    – Kaveh
    Commented Apr 26, 2011 at 9:03
  • $\begingroup$ 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. $\endgroup$
    – Antonio Valerio Miceli-Barone
    Commented Apr 26, 2011 at 13:46
  • $\begingroup$ As I said, universality does not care about the complexity issues like being exponentially slower. $\endgroup$
    – Kaveh
    Commented Apr 27, 2011 at 6:01
  • $\begingroup$ 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? $\endgroup$
    – Antonio Valerio Miceli-Barone
    Commented Apr 27, 2011 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.