×

A note on off-line machines with ’Brownian’ input heads. (English) Zbl 0553.03026

The author introduces off-line Turing machines with read-only input tape, where the machines cannot control and observe the moves on the input tape. The input tape has a left endmarker and a different right endmarker. In case of an input system regular languages as \(a^*\), \(a^ t\), \(\{a_ 1,...,a_ n\},\) \(\{\emptyset,a_ 1,...,a^ n\}\) can be accepted only. For languages with 3 symbols moves can be observed by looking at \((cab)^ n\) words. This can be used to show that every rec. enumerable language can be accepted. For binary languages it is proved that these languages are regular. The proof is not constructive and based on a well-partial order generated by so called random input sequences. One has the feeling that these binary languages are quite simple.
An example of a regular language is missing, which cannot be accepted by this kind of machines. Such a counter example is the language \(\{a^ ib^ ja^ rb^ s(ab)^ n| n\in N\}\) for some fixed i, j, r, s.
Reviewer: H.Kleine Büning

MSC:

03D10 Turing machines and related notions
68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI

References:

[1] Haines, L. H., On free monoids partially ordered by embedding, J. Combin. Theory, 6, 94-98 (1969) · Zbl 0224.20065
[2] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, (Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0155.34303
[3] Kruskal, J. B., The theory of well-quasi-ordering: a frequently discovered concept, J. Combin. Theory (A), 13, 297-305 (1972) · Zbl 0244.06002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.