5
$\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 non-standard way) $\Sigma^*$ to denote possible tape contents with finitely many non-blanks).

(basicaly the idea is that we always can encode the input, let $M$ run on it and decode output so that we compute any computable function)

However, there are many machines which are "weakly universal", for example machines which simulate rule 110. My question is, what does that mean? These notions are usually understood to be intuitive by community, but I have never managed to find a (semi)formal definition of universality. Indeed, most sources that call machines like Wolfram's (2,5)-TM (weakly) universal define universality as "able to simulate any Turing machine", whatever that means. 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 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.

Thanks in advance for all the answers.

$\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

Your Answer

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

Browse other questions tagged or ask your own question.