7
$\begingroup$

The first part of this question has been solved (see comments).

In the book "computational complexity" by Papadimitriou, a Universal Turing Machine is given. But this machine is not concrete, in the sense that it contains variable parameters. For example, the states of the input Turing Machine are represented as binary strings of fixed length. Hence, no matter how long we let this length be, there will always be Turing Machines with so many states that they cannot be represented. Can this machine then really be called a UTM, or at least a template for a UTM?

I also read that a 2-state, 3-symbol UTM has been discovered. This would mean that the action table contains only 6 entries. Am I right in my conjecture that such a machine must have a very complex encoding of the input TM?

Improve this question
$\endgroup$
5
  • $\begingroup$ There is more than one notion of "computational universality" and they are probably not all equivalent. You could take a look at the links in Andrej Bauer's answer to this question: cstheory.stackexchange.com/questions/1037/… $\endgroup$
    – Aaron Sterling
    Commented Sep 11, 2010 at 20:19
  • 2
    $\begingroup$ “the states of the input Turing Machine are represented as binary strings of fixed length.” You must have misunderstood something written in the book. In fact, Papadimitriou explicitly states the opposite: “Since U must simulate an arbitrary Turing machine M, there is no a priori bound on the number of states and symbols that U must be prepared to face.” (Section 3.1, the second paragraph.) $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 11, 2010 at 20:52
  • 6
    $\begingroup$ Both of these comments could (and should) be answers ! $\endgroup$
    – Suresh Venkat
    Commented Sep 11, 2010 at 21:11
  • 1
    $\begingroup$ @Suresh: Thanks for the comment, but I will not post my previous comment as an answer. Although I sometimes post a comment as an answer (and vice versa), my opinion is fairly firm that my previous comment is not an answer, and I do not think that I can answer the question appropriately because I do not know the source of confusion by the questioner. I hope that my comment gives him a nudge to the right direction so that he can answer the question by himself. I am hoping that when he knows the answer he will post it so that it will help some other people who wonder the same thing. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 11, 2010 at 21:43
  • $\begingroup$ @Tsuyoshi I was aware that he stated this at the beginning of the discussion of UTMs, but thought that the later definition he gives contradicts this statement. Now that I read it carefully once more, I found that I misunderstood something: All states for a given input TM are encoded as binary strings of the same length, not for all input TMs are the states encoded as fixed length binary strings. $\endgroup$
    – Martin
    Commented Sep 11, 2010 at 22:48

2 Answers 2

Reset to default
12
$\begingroup$

In response to your second question, you are correct -- a 2-state, 3-symbol state TM was shown to be universal by then-undergraduate Alex Smith in 2007 by reduction to a universal cyclic tag system, which makes for a complex encoding. Here's the original proof, which uses Wolfram's nonstandard notation for representing Turing Machines.

It's easy to intuit why simpler universal Turing Machines require more complicated encodings -- after all, the information involved in the computation needs to go somewhere. For example, in the encoding scheme implicit in Smith's proof, we would first need to first encode the Turing Machine under simulation within a cyclic tag system, then use Smith's scheme to represent the cyclic tag system within the 2-3 Turing Machine.

Improve this answer
$\endgroup$
6
$\begingroup$

There is more than one notion of "computational universality" and they are probably not all equivalent. You could take a look at the links in Andrej Bauer's answer to this question.

-- per Suresh's suggestion.

Improve this answer
$\endgroup$

Your Answer

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