Lisp and the foundations of computing

Posted Feb 18, 2019 23:12 UTC (Mon) by nix (subscriber, #2304)
In reply to: Lisp and the foundations of computing by Wol
Parent article: Lisp and the foundations of computing

As soon as you start studying turing complete languages, the maths says they are equivalent, which means that they are in fact the same thing.

Up to a point, Lord Copper. They are equivalent given an infinite tape and infinite time, and ignoring everything other than pure computation. I/O, random number generators, the time of day, anything at all to do with space or time complexity -- suddenly you are out of the Turing tarpit and languages and Turing-complete systems are distinguishable once more. i.e. just because you can emulate any Turing-complete system in any other doesn't mean you can emulate it at the same speed or in the same space.

So our systems are strictly more powerful than Turing machines -- but since infinite storage and time are not remotely feasible, we have also got no access to anything with the computational power of a "real" Turing machine, nor ever will. (And, of course, there is an unboundedly infinite hierarchy of Turing oracles, each of which can solve the halting problem in lower orders of oracle and in Turing machines themselves. We have even less idea how any of these might work: probably the answer is "they are defined by assertion and are not just unphysical but logically impossible entities".)