Hacker News new | ask | show | jobs
by wang_li 1032 days ago
A demonstration of Turing equivalency. Any Turing complete computer can do what any other Turing complete computer can do if you don’t care about time.
2 comments

Time and memory.
Yeah, so technically a Turing machine has infinite memory.. so no real-world computer is fully Turing complete.
A Turing machine has infinite tape. Which can be implemented in terms of RAM but can just as well be implemented in terms of sequentially addressable IO, and pretty much every real-world computer has that, so it's a meaningless technicality as while there are practical limits on our ability to feed it more input, those are not conceptual limits of the machine.
How do you run Linux in lambda calculus?
Slowly. Very slowly.