# Decision problems involving finite automata

A finite automaton (FA), A, may accept or reject its own encoding, {A}. A machine, M, can be written that accepts {A} iff A rejects {A}. Turing gave a famous proof that M is not an FA. The proof relies on a contradiction that occurs when one assumes M is an FA and then runs M on its own encoding. However, it may still be possible that M is an FA that correctly decides a large class of inputs other than {M}.

I’d like to know what’s in that class, so I’m interested in finding prior work done on this topic. Can anyone point my towards the relevant literature?

• – Yuval Filmus Dec 16 '18 at 19:01
• The answer depends on $M$, of course. A more interesting question could be the following. Is there a linear countable hierarchy of $M$ that can accept increasingly more such $A$ and all of them can accept all such $A$? – Apass.Jack Dec 16 '18 at 20:50