On the multiplying ability of two-way automata

摘要

It is shown that multiplication and square root extraction can be performed by the two-way automata of Kreider and Ritchie, thus answering questions raised by those authors. Square root extraction is straightforward (yielding an integer root and a remainder), but multiplication is achieved only by conversion of the input data from binary to ternary notation. In effect the Kreider-Ritchie machine can be and is here used as a weak linear bounded automation (Turing machine with access limited to k1l+k0 tape cells when the input length is l cells) with k1=1,5, whereas it was intended to have k1=1. The possibility of multiplication in the strict k1=1 case remains unknown.