3 ms·
"It was a self-contained, Turing complete, programmable machine no larger than a suitcase" - False Languages can be Turing complete. ISAs (Instruction Set Arch
by Nomentatus 9y ago
"It was a self-contained, Turing complete, programmable machine no larger than a suitcase" - False
Languages can be Turing complete. ISAs (Instruction Set Architectures) can be Turing complete. Machines... um, no, not of present design. That infinite tape provides infinite memory including infinite register space. Hard to duplicate with a real machine. There's a limit to the largest number you could square on an IBM PC, so it's not Turing complete - in other words, there are functions it can't calculate, even given infinite time.
- khedoros1 9y agoWhen people say that a physical machine is Turing-complete, they invariably mean that it is equivalent to a linear-bounded automaton, precisely because an infinite tape isn't possible for us to construct.