𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the multiplying ability of two-way automata

✍ Scribed by J.R.H. Dempster

Publisher
Elsevier Science
Year
1968
Tongue
English
Weight
292 KB
Volume
2
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 kal + ho tape cells when the input length is 1 cells) with kl = 1.5, whereas it was intended to have k x = 1. The possibility of multiplication in the strict k 1 = 1 case remains unknown.

πŸ“œ SIMILAR VOLUMES

On two-way tree automata
On two-way tree automata
✍ Etsuro Moriya πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 323 KB
On two-way multihead automata
On two-way multihead automata
✍ Oscar H. Ibarra πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 479 KB

For each positive integer n, let -~eN(n ) be the class of sets accepted by a family of automata of type N, each with a read-only input with endmarkers and n two-way input heads. The following result, which is applicable to most types of two-way multihead devices, is proved: If for each positive inte