The Computation of Partial Recursive Word-Functions Without Read Instructions
✍ Scribed by Holger Petersen
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 422 KB
- Volume
- 42
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
In this note we consider register‐machines with symbol manipulation capabilities. They can form words over a given alphabet in their registers by appending symbols to the strings already stored. These machines are similar to Post's normal systems and the related machine‐models discussed in the literature. But unlike the latter devices they are deterministic and are not allowed to read symbols from the front of the registers. Instead they can compare registers and erase them. At first glance it is surprising that in general these devices are as powerful as the seemingly stronger models. Here we investigate the borderline of universality for these machines.
Mathematics Subject Classification: 03D20, 68Q05, 68Q10.