9
$\begingroup$

For what I know, the definition of a universal Turing machine is something along the lines of the following (of course, details might vary from source to source):

A Turing machine $M$ is called universal if there are computable functions $f:\Bbb N^2\rightarrow\Sigma^*$ and $g:\Sigma^*\rightarrow\Bbb N$ such that for any $e,n\in\Bbb N$, $\varphi_e(n)$ is equal to $g$ applied to output of $M$ on input $f(e,n)$ (here I use (in a non-standard way) $\Sigma^*$ to denote possible tape contents with finitely many non-blanks).

(basicaly the idea is that we can compute any computable function by encoding the input, letting $M$ run on it and then decoding the output)

However, there are many machines which are "weakly universal", for example some machines which simulate Wolfram's Rule 110 automaton. The "weakness" here refers to the fact these machines require one to introduce some "background" into the encoding, usually periodic, but sometimes not (e.g. for the (2,3)-TM).

My question is, what does that actually mean? These notions are usually understood to be intuitive by the community, but I have never managed to find a (semi)formal definition of universality which would apply to them. Indeed, most sources that call machines like Wolfram's (2,5)-TM (weakly) universal define universality just as "able to simulate any Turing machine", whatever that is supposed to mean. I have decided to make my question specific as follows:

Under what (formal) definition of universality is Wolfram and Cook's (2,5)-TM (I couldn't find a better reference) universal? How about Wolfram's (2,3)-TM?

I suspect this might have been asked before, but I couldn't find anything by searching. (Edit: and 4 years later I still am unable to locate one!)

$\endgroup$
  • $\begingroup$ From what I understand, in a standard UTM the tape is considered to be entirely blank (or all 0's) to the left and right of the input at the start of execution, whereas in a weakly UTM there can be (possibly different) infinitely repeated words to the left and right of the input. This is corroborated by this paper, which also adds the definition of semi-weakly UTM, where the tape has an infinitely repeated word on one side and all 0's on the other side. I suppose the output is whatever is written by the head during execution. $\endgroup$ – Deedlit Jan 13 '16 at 3:55
  • $\begingroup$ Sorry, I guess neither of those machines satisfy any of those definitions! The second answer from this CSE question seems to give a good overview on how Rule 110 is turned into a computing machine. More details are availabe in Cook's paper. $\endgroup$ – Deedlit Jan 13 '16 at 4:13
1
+200
$\begingroup$

Let us first start with the main question: in his paper, Cook claims that Rule $110$ is universal in the classical sense of being able to simulate any Turing machine. Now, there is the (inessential) subtlety that (classical) Turing machines are required to halt, while cellular automata never halt. This is not crucial, as you can change every terminating TM into a never-halting one by changing it so that, when it reaches the halting state, it actually enters a loop and print a special character, say H, on the tape. Using this simple trick, if you can use a cellular automata to simulate a TM then you can also recognize when such a TM actually reaches the end of the computation (just by checking whether it prints H).

Hughes, in his work, claims to have found a gap in Cook's proof, but also to have a fix for it. As a consequence, Wolfram and Cook $(2,5)$-TM is universal, in the classical sense of being able to simulate any Turing machine.

For the $(2,3)$ machine, I would expect that, again, universality is claimed in the classical sense. I couldn't find the proof itself, I only found a sketch of the ideas here. Also, there's a post about it on Wolfram's blog.

For the name "weak Turing machine", the notion is defined in this paper by Neary and Woods. I am not sure whether it is the first time that such Turing machines are given a name. For example the authors claim that the first example of a weak UTM was produced by Watanabe in his 1961 work, even though I don't see it explicitly called "weak UTM" there. Quoting Neary and Woods

One variation on the standard model is to allow the blank portion of the Turing machine’s tape to have an infinitely repeated word to the left, and another to the right. We refer to such universal machines as weakly universal Turing machines, and they the subject of this work.

In a later work they also introduce the notion of "semi-weakly TM", by allowing the machine to "have an infinitely repeated word to one side of the input and an infinitely repeated blank symbol to the other side".

EDIT: Let me try to elaborate a bit the points we discussed in the comments. The question "what is the precise definition of translations we admit?" is certainly a good question. Let me make a small digression, maybe you are already familiar with some of these things but I feel they are useful to the explanation.

Let us start with partial recursive functions as our "standard" model of computation: you start from a small set of functions, called primitive recursive, and you close it under primitive recursion and minimization. The set of primitive recursive functions are intuitively computable, so you want them to be computable. Hence you choose them as a starting point, in other words you define them to be computable. If you start from a larger set of functions, where you put some complicated function among the primitive recursive, you end up with a larger set of partial recursive functions (and this is actually the beginning of relative computability).

Let us now consider TMs. Let us assume that we are working with $2$-symbols machines (+ blank), a single infinite tape, single head. They are a different object entirely, mathematically speaking they are defined as tuples. So what does it mean that such a tuple computes some function? Well, you usually fix a way to code numbers into the tape, then you "let the machine run" (a notion that can be defined formally, but whose intuitive meaning is much stronger) and then decode the output.

Now notice that there is already a translation involved here: we want to translate a number into a binary string that encode your number. Now if the symbols of your machine are, say, $A$ and $B$, how can you say that the translation from natural numbers to strings of $A$ and $B$ is computable? This is not a map $\mathbb{N}\to\mathbb{N}$, and you didn't define a notion of computability on functions $\mathbb{N}\to\{A,B\}^*$. The truth is: this is intuitively computable, so you define it to be computable. Same for the function $\{A,B\}^*\to\mathbb{N}$ that decodes the output.

You are perfectly right in saying that, choosing a very "complicated" function you can make computable things that are not (or rather should be not). In fact, to be precise, you should always say you are defining $(\delta,\delta^{-1})$-computability on maps $\{A,B\}^*\to \{A,B\}^*$, where $\delta$ and $\delta^{-1}$ are encoding and decoding functions.

The maps $\delta$ and $\delta^{-1}$ are, very often, omitted, especially in classical computability. They become way more relevant when it comes to computable analysis, where you define a notion of computability on "more general" spaces than $\mathbb{N}$ (they are called "represented spaces", e.g. $\mathbb{R}$ or $2^\mathbb{N}$). If you want to know more, a starting point could be Weihrauch, Computable Analysis. For classical computability they are omitted because "it is intuitive that they are computable". For example, if instead of $\{A,B\}$ I choose $\{0,1\}$ as symbols, then you can prove that the function that maps $n$ to the number whose decimal representation is the same as the binary representation of $n$ (e.g. $2\mapsto 10$) is computable (i.e. is recursive). Still you may argue that going from the number $10$ to the string $10$ is not something I proved to be computable. Indeed, that's why I define such an operation to be computable, confident that no-one will argue against that (like I expect nobody to complain if I replace $A$ with $0$ and claim that it is a computable operation).

Let's now move to the OP. First let me elaborate why it is not crucial to work with halting machine. If you agree that $2$-symbols TMs are equivalent to $3$-symbols machines then consider the following: start from a $2$-symbol machine and replace the halting state with a (non-halting) state $Q$. Add also a transition rule that says that if you are in $Q$ then the machine remains in $Q$, prints $2$ and goes right. Such an operation can be proved to be computable (you have to represent the machine as a number and show that mapping this number to the code of the modified machine is a computable function $\mathbb{N}\to\mathbb{N}$. Gödel did something similar with arithmetic formulas, and I bet everyone just agrees that is doable). So now every non-halting machine is still non-halting, but now every halting machine is mapped to a non-halting one. We then defined a bijection from the $2$-symbols machines to a subset of the $3$-symbols machines, s.t. a $3$-symbols machine prints $2$ iff the corresponding $2$-symbols machines halt. Thus working with such a subset of the $3$-symbols machines is equivalent to working with $2$-symbols (halting) machines.

Let us now turn to the infinite input issue. Let me elaborate why an infinite periodic is not (necessarily) an issue. Assume the input you want to build is something like $s \rho^\omega$ where $s$ is a finite string and $\rho$ is the finite string which is repeated infinitely often (the reasoning is the same if you want a infinite string on the left as well) and assume $T$ is a TM that runs on such an infinite input. How can we simulate the behavior of $T$ with a classical TM, say $M$? well, you can do the following: mark the end of $s$ with a special symbol $H$. The machine $M$ works as $T$ except in the following situation: when $M$ reads $H$ it enters a special state: it prints a copy of $\rho$ on the right hand of the tape and ends it with $H$, then moves the head back at the beginning of $\rho$ and continue the execution of $T$. Since $\rho$ is finite you can hardcode it into $M$ without affecting the computability. If you want to phrase the same argument in terms of partial recursive functions you can probably use the $smn$-theorem, but I hope this level of detail is ok.

Notice that there are two reasons why the computability power is not affected: first classical TMs work "locally". They only see one symbol at a time. This can be formalized by saying that computable maps are continuous (the notion of continuity is of course based on topology, again I refer to the book of Weihrauch for more details). The second is that every finite string can be hardcoded into a TM, hence we can do the trick I mentioned above. Of course, if you allow for arbitrary infinite input to be coded on the tape as input, then the computability power increases, so, in general, TM that allow infinite non-computable input can produce non computable outputs.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I had to hunt around a bit but the proof that (2,3) is universal is here: wolframscience.com/prizes/tm23/TM23Proof.pdf It looks like it was never published. (Wolfram wrote that it would be published in Complex Systems.) $\endgroup$ – Carl Apr 20 at 16:36
  • $\begingroup$ The PDF above is linked to from here where there is a technical summary. $\endgroup$ – Carl Apr 20 at 16:43
  • 2
    $\begingroup$ Thank you for this answer and references therein. However, unfortunately, it doesn't seem to me that this answer addresses the main question I have posed, which is what does universal computation mean in this context. You say (or cite Cook saying) that "Rule 110 is universal in the classical sense of being able to simulate any Turing machine", but Cook's paper doesn't seem to address the question of how this classical sense is formally defined. $\endgroup$ – Wojowu Apr 21 at 21:34
  • $\begingroup$ @Wojowu Not sure I understand your question then. You are writing yourself the definition of universal TM (details of the formalization are often different in a non-essential way). Cook proves (or claims at least) that Rule $110$ is universal in the sense that it is able to simulate the computation of any (classical) TM. There is a bit fixing needed to match the fact that TM are required to halt while CA do not, but as I explained, simulating the computation of a non-halting machine is enough. $\endgroup$ – Manlio Apr 21 at 23:18
  • 3
    $\begingroup$ These machines certainly are not universal in the sense I have specified, even if we somehow modify it to admit non-halting machines (and it's not clear to me how one would do that), since we somehow have to admit machines running on infinite inputs. $\endgroup$ – Wojowu Apr 21 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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