7 ms·
It can, however, be arbitrarily long.
by gchpaco 17y ago
It can, however, be arbitrarily long.
- _delirium 17y agoBut even so, it's no more powerful than a finite state machine if the tape length is finite.
- cschneid 17y agoTuring machines don't define speed. So if the human is willing to get notified of a tape overrun, and splice on more tape, it is infinite.
- neilc 17y agoExcept that the computational capacity of the universe is finite (see http://arxiv.org/abs/quant-ph/0110141 http://arxiv.org/abs/quant-ph/0110141).
- jvdh 17y agoI remember that the Universal Turing machine needs an infinite tape. But I don't think you'd need one in practice. Besides, memory and states in modern computers are finite too, and they're all Universal Turing machines.
- cracki 17y agoright. the tape only has to be $steps long, for $steps steps of computation, because that's the longest distance the head can travel at all. any program that eventually halts, has a finite number of steps, so the band can be finite. the only thing that requires an infinite band, is a non-halting program. and non-halting programs (unlike real-world servers and OSes) don't have a result as defined by the turing machine concept.
- argv_empty 17y agothe only thing that requires an infinite band, is a non-halting program. Sure, that's the only type of program that would use the whole tape, but given any tape of finite length, there's a (program, input) pair that needs a longer tape.
- tetha 17y agoI'd argue that our computers are no universal turing machines, but they surely are close enough for everyones needs. Just like the ocean is infinite if you try to swim through it, even though a plane crosses it in a few hours.
- almost 17y agoNot quite, in practice they are pretty much equivalent but they're not Universal Turing Machines. For that they would need to have infinite memory. A Universal Turing Machine is a theoretical construct, it's not something that could actually exist.
- jvdh 17y agoI 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.
- almost 17y agoYour 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 :)
- cschneid 17y agoPause machine, find new universe.