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?

  • $\begingroup$ See stackoverflow.com/questions/2466770/…. $\endgroup$ – Yuval Filmus Dec 16 '18 at 19:01
  • $\begingroup$ 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$? $\endgroup$ – Apass.Jack Dec 16 '18 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.