On the hartmanis-stearns problem for a class of tag machines

Abstract

An infinite sequence over a finite alphabet is regular if the indices of those positions at which each given symbol occurs in the sequence constitute a set of numbers which in suitable base is recognizable by a finite automaton. A sequence obtained by deleting from a regular sequence all occurrences of certain symbols is semi-regular. Semi-regular sequences are alternatively characterizable as those which are the real-time generable output of tag machines with deletion number one, regular sequences as those generable by such machines additionally constrained to have tag productions with consequents of uniform length. A real number is called regular or semi-regular if its expansion in some base is a sequence of corresponding type. As a consequence of the fact that the operation of a tag machine can be described by a system of functional equations of standard form, it can be shown that no regular real number is algebraic irrational. This generalizes to include those semi-regular reals generable by tag machines in the operation of which the gap between read head and write head increases proportionately with time. The status of the semi-regular reals not generable in this fashion is left open.