5
$\begingroup$

I've read what's a Turing machine and an UTM are, but I don't get the difference. What does an UTM can do which a normal Turing machine can not?

$\endgroup$
5
$\begingroup$

A universal Turing machine is just a Turing machine whose programming simulates other Turing machines. That is, the input to the UTM is a description of a Turing machine $T$ and an input for $T$, and the UTM simulates $T$ on that input.

It's universal in the sense that, for any problem that can be solved by Turing machines, you could either use a Turing machine that directly solves that problem, or you could use a UTM and give it the description of a TM that directly solves the problem.

If you like, a UTM is an interpreter for (all) Turing machines.

$\endgroup$
  • $\begingroup$ It is also (one of) the first description(s) of a stored-program computer. $\endgroup$ – Jörg W Mittag Jan 24 '17 at 11:18
  • $\begingroup$ @JörgWMittag Good point. Was it thought of in those terms in the 1930s? $\endgroup$ – David Richerby Jan 24 '17 at 11:22
  • $\begingroup$ I don't think so. After all, it wasn't even thought of as a computer at all. Or rather, it was thought of as what was at that time called a computer, namely a human who computes logarithm tables etc. by hand. That's how Turing came up with his model: a pen, a piece of paper, a (limited) vocabulary, a (limited) memory, and a (limited) set of rules. $\endgroup$ – Jörg W Mittag Jan 24 '17 at 12:03
1
$\begingroup$

A UTM can run any Turing machine on some input.

A Turing machine can be compared to a program. It takes some input and generates some output.

A UTM can be compared to a computer. It can take any program and run it with some input and generates some output.

The UTM is a Turing machine in itself, so the interesting idea here is that any Turing machine can be encoded as input understood by another Turing machine.

$\endgroup$
  • 1
    $\begingroup$ I think you have to be careful with this analogy. A Turing machine feels more like a special-purpose computer, to me: it's a "physical" device. But I suppose that part of the point is that these devices can be described as something like programs. $\endgroup$ – David Richerby Jan 23 '17 at 20:00
1
$\begingroup$

Every TM does just one task. It sums two input numbers, or it scans the input for some symbol, or it looks for a counterexample of Goldbach's conjecture ...

... or it (let us call it TM#1, since we will have a 2nd one shortly) gets two parts of input, where the first describes a TM, TM#2 (think of a (fixed) TM as a finite number of states and transitions and stuff like head directions) and next to the description of TM#2 a description of input to TM#2.

So TM#1 receives the pair ("TM#2" "input#2") as its input#1. And then TM#1 runs on this input#1 and behaves (to the outside, after termination!) as if it was TM#2 working on input#2. In case TM#2 would not halt, TM#1 won't do either.

Such a TM#1 is called a UTM, since it can behave like/fake/simulate any other TM you give it as TM#2. Think of a virtual machine (TM#1), a simulated program (TM#2), and an input to the simulation (input#2). The VM takes longer, but the results are the same.

Even TM#2 = TM#1 is possible ... then input#2 = ("TM#3" "input#3") and TM#1 is a UTM and now simulates another UTM (TM#2) which in turn meta-behaves as TM#3 on input#3, in symbols:

TM#3(input#3) = TM#2("TM#3 input#3") since we took TM#2 to also be a UTM = TM#1("TM#2 'TM#3 input#3'")

Again: Behaviour is in terms of eventual final output, if and when halting, certainly not in terms of tape contents at any time, number of time steps etc., simulation takes (much) more time than doing it directly.

$\endgroup$

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.