3 ms·
Mapping N Turing Machines (“K-Tape”) – Into a Single-Tape Turing Machine
- peter_d_sherman 7y agoGoogling for a simple C Compiler that compiles to a Turing Machine (to potentially help answer another HN post about wanting to learn assembler), I stumbled upon the following page: https://cstheory.stackexchange.com/questions/18688/a-small-c-like-language-that-turing-machines-can-simulate https://cstheory.stackexchange.com/questions/18688/a-small-c... Which had the following comment, by GMB: "My Theory of Comp professor in undergrad started by proving that a single-tape Turing machine can implement a multi-tape Turing machine. This handles variable declaration: if a program has six variable declarations, then it can be easily implemented on a seven-tape Turing machine (a tape for each variable, and a "register" tape to help perform tasks like arithmetic and equality-checking between tapes). He then showed how to implement basic FOR and WHILE loops, and at that point we had a basic Turing-complete C-like language. I found it satisfying, anyways." I would have found that last part satisfying too... But what I really found satisfying is the statement: "a single-tape Turing machine can implement a multi-tape Turing machine", because before reading this, I didn't know that a Single-Tape Turing Machine -- could in fact simulate N ("K-Tape" in academic parlance) other Turing machines in its space... Which is truly fascinating... It makes sense, if we think about machine virtualization. A virtualized machine can simulate another virtual machine, which can simulate another, as long as there's enough memory -- turtles all the way down, as the saying goes... But usually virtual machines are complex and instruction set bound, and Turing Tapes / Turing Machines are simple, much simpler (perhaps orders of magnitude simpler) abstractions for any form of computation... It just makes a lot of sense. Utterly fascinating, IMHO... Anyway, links and comments on this subject appreciated...