Foreground automata

摘要

This paper defines a class of on-line foreground automata, which make distinctions between the “foreground” or relevant inputs and outputs and the “blank” ones that serve as a background. It is shown that there is a well-defined operation that maps the substring of relevant inputs into an eventually appearing substring of relevant outputs, without regard for the blanks scattered among the inputs. This operation plays the role of the computation of an off-line automaton and a computational time can be measured by comparing the automaton to a “benchmark automaton” that produces each relevant output as soon as theoretically possible. Properties of these computational times are explored, both for finite automata and “Turing automata,” which are modeled by multi-tape Turing machines. An analogue of Church's Thesis can be stated for the computations associated with the operations of Turing automata, but it is argued that there is no clear cut formalization for the concept of an “effective foreground automata.”