Two Dimensional Turing Machines

Turing in his immortal 1936 paper observed that “computing is normally done by writing… symbols on [two-dimensional] paper”, but that “the two-dimensional character of paper is no essential of computation.” I believe that the two-dimensional model is in fact much more intuitive than the standard one-dimensional version that we teach, and that it is readily programmable. In particular, programs for a two-dimensional Turing machine can themselves be recorded naturally in a two-dimensional format in such a transparent fashion that schoolchildren have no difficulty comprehending and emulating their behavior. Such a two-dimensional rendering allows, furthermore, for a most perspicacious rendering of Turing’s universal machine.

hosted by