Hacker News new | ask | show | jobs
by Laakeri 2046 days ago
All Turing-complete programming languages/models of computation can simulate each other with polynomial overhead. What I think is weird is that the article specifically mentions that programming languages are built on single tape Turing machines (as opposed to Turing machines in general, or random access machines), because single tape Turing machines are highly impractical and programming them would feel completely different than programming with any real programming language. For example as basic operation as array access takes a linear number of operations in the size of the array in the single tape model.