# Class of languages recognised by a Forgetful Turing Machine

A Forgetful Turing Machine (FTM) operates just like a normal Turing machine except that, in every instruction (i.e., transition), the letter written in the tape cell is always the letter $$a$$, regardless of the current state and the current letter (although the read/write head is still allowed to move either Left or Right, according to the instruction). What class of languages is recognised by FTMs?

Is the language non-empty with only the letter $$a$$? Does this mean that it is regular since it can be represented by $$aa^*$$?

• Your model can certainly simulate DFAs. Make sure you understand the definition of the language accepted by a forgetful Turing machine. – Yuval Filmus Sep 22 '19 at 13:52
• @YuvalFilmus since DFAs recognises regular languages, this also implies that FTMs is recognised by a regular language, right? – llamaro25 Sep 22 '19 at 14:02
• I’d say the implication goes the opposite way. – Yuval Filmus Sep 22 '19 at 16:33
• This is an interesting and somewhat tricky question but you seem not to understand the basic definition of a language recognized by a machine. Maybe it is better to ask the one who assigns this question to you for help. – xskxzr Sep 22 '19 at 18:42
• @xskxzr I did but I still did not understand. Are there any hints on how to approach this question? – llamaro25 Sep 23 '19 at 6:54

The class languages recognized by FTMs are the class of regular languages. A FTM can completely simulate a DFA, so each regular language can be recognized by a FTM. On the other hand, if we can prove each FTM recognizes a regular language, we have proved the assertion.

Given a FTM $$F$$ with the set of states $$Q$$, we use the Myhill–Nerode theorem to show the language it recognizes is regular. Given a string $$x$$, we ask the following query:

1. If $$F$$ runs on $$x$$, does $$F$$ ever leave $$x$$ to the right? If so, in which state is $$F$$ when it first moves to the first position to the right of $$x$$? If not, does $$F$$ accept $$x$$?

... and the following $$|Q|$$ queries for each state $$q\in Q$$:

1. If $$F$$ runs on $$\underbrace{a\cdots a}_\text{the number of a = |x|}$$, but is started on the rightmost $$a$$ and in state $$q$$, does $$F$$ ever leave the input to the right? If so, in which state is $$F$$ when it first moves to first position to the right of the input? If not, does $$F$$ accept the input finally?

We collect the strings that give the same answers to the $$|Q|+1$$ queries above into the same class. Since there are $$(|Q|+2)^{|Q|+1}$$ possible answers to the $$|Q|+1$$ queries above, there are only finite many classes. Next, we are going to prove that for any strings $$x,y$$ in the same class, i.e., that give the same answers to the $$|Q|+1$$ queries, for any string $$z$$, $$F$$ accepts either both or neither of $$xz$$ and $$yz$$, which completes the proof by the Myhill–Nerode theorem.

Consider that $$F$$ runs respectively on $$xz$$ and $$yz$$. Note the answers to query 1 are the same for $$x$$ and $$y$$, there are two cases:

1. $$F$$ never leaves $$x$$ to the right on $$xz$$, and $$F$$ never leaves $$y$$ to the right on $$yz$$. In this case, $$F$$ runs as if the inputs are respectively $$x$$ and $$y$$. Since the answers to query 1 are the same for $$x$$ and $$y$$, $$F$$ accepts either both or neither of $$xz$$ and $$yz$$.
2. $$F$$ ever leaves $$x$$ to the right on $$xz$$, and $$F$$ ever leaves $$y$$ to the right on $$yz$$. In this case, $$F$$ is in the same state when it first moves to the leftmost position of $$z$$, so $$F$$ behaves the same until it returns respectively to the rightmost position of $$x$$ and $$y$$. According to the definition of FTM, the input must become $$a\cdots a$$ when $$F$$ returns, and we can apply a recursive analysis according to query 2 (you can use mathematical induction to write a strict proof). As a result, $$F$$ accepts either both or neither of $$xz$$ and $$yz$$.

Of course, the analysis above assumes the tape of the FTM is restricted such that the head cannot leave the input to the left. The proof is similar without this assumption.