A note on off-line machines with 'Brownian' input heads (Q801900): Difference between revisions

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.