How powerful are turing machines that can’t erase?
A fun link that I can’t track down explained that the reason that graduate students are forced to do research and write papers is best explained by analogy to computational complexity: DFAs, by themselves, can’t do much. But turing machines can do almost anything – and a turing machine is just a DFA with a pen!
If we combine this insight with an old joke:
Dean, to the physics department. “Why do I always have to give you guys so much money, for laboratories and expensive equipment and stuff. Why couldn’t you be like the math. department – all they need is money for pencils, paper and waste-paper baskets. Or even better, like the philosophy department. All they need are pencils and paper.”
We can begin to wonder… how powerful are the computers in the philosophy department? How powerful can a turing machine be if it can’t erase any marks on its tape?
It’s not clear that a single-tape turing machine on a WORM is more powerful than a DFA. With two tapes, the turing machine can at least solve the PALINDROME problem, but how much power is required for, say, log-space computation? How many tapes are required for the standard complexity classes?
Because, all of a sudden, you can’t reuse space OR time. I think this is a neat idea, and it may have applications to reversible computation and to parallel computation.
