A language is regular if it is accepted by a read-only Turing machine. I am curious about applying this model to functional problems rather than decision problems.
Definition: A functional read-only Turing machine is a read-only Turing machine with a generic HALT state (but no ACCEPT or REJECT states). On input $x$, it returns an integer between $1$ and $|x|+1$ (where $|x|$ is the length of the bit representation of $x$), corresponding to the bit of the input on which the machine halted (or $|x|+1$ if the machine halted on the string of blanks off to the right of the input).
Definition: A regular function is a function accepted by a functional read-only Turing machine.
Now, my questions:
Have regular functions been studied before? If so, do they have a name in the literature? What is known about them?
Regular languages have a very nice analytic characterization (that is, they are the closure of the singleton languages under union, composition, and Kleene star). Is there a similar characterization for the regular functional languages?
Thanks for reading!
A good example of a regular function is the problem of locating a substring within the input. For example, suppose we want to output the index of the first substring "01" within the input on a binary TM (or indicate that no such substring exists, by returning $|x| + 1$). We implement with the following read-only functional TM:
Where S is the start state, H is the halting state, and X, Y are additional states. This machine will always halt with its tape head positioned over the 0 in the first "01" substring, which "returns" the index of that substring.