Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I did some more research and digging through my books.

A Universal Turing machine is one that can read programs from its own tape.

Infinite tapes are necessary for the halting problem, to allow programs to run infintely on infinite memory.

Turing Completeness is when the machine is proven to be equivalent to a Turing Machine, i.e. it can be programmed to solve any algorithmical problem.



Your definition is slightly wrong. In Alan Turing's own words:

    It is possible to invent a single machine which can be used
    to compute any computable sequence. If this machine I is
    supplied with a tape on the beginning of which is written the
    S.D of some computing machine M, {242} then I will compute
    the same sequence as M.
(Alan Turing, 1936, On Computable Numbers, With An Application To The Entscheidungsproblem)

So it is no merely that the Universal Machine can read and execute programs, it is that it can read and executes programs to make itself equivalent to ANY other turing machine. Thus the Universal Turing machine is Turing Complete. As the amount of tape required to solve all computable programs is unbounded the Universal Turing machine must have an infinitely long tape.

It's usually worth going straight to the source where you can in CS, but much more so with Turing as his papers are so nice and easy to read :)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: