[SOLVED] Is it possible to write a self-interpreting FSM or Pushdown Automaton?

Is it possible to write a self-interpreting FSM or Pushdown Automaton?

I'm sorry for this newbie question, but I need a quick answer to tell a friend if that's possible.

Solution

Wow. A lot of answering this question comes down to deciding what such a thing means.

The quick answer is "No".

You can interpret a program written in a language. You cannot 'interpret' an FSM. What you can do is have one FSM emulate another. In a trivial and uninteresting way an FSM can emulate itself. An FSM can also be set up to emulate another FSM that is smaller than it. It can't, in general, emulate an FSM that is larger than it. It has too few states in total to represent the states of the larger FSM.

Whether an FSM can be considered to emulate itself in a non trivial way is down to semantics. Consider an FSM that generates the sequence 1,1,1,1. Now look at every second output. It's exactly the same sequence. The same thing goes for an FSM generating the five step sequence 1,0,1,1,1, repeatedly. The intriguing behavior of an interpreter that interprets itself - that you see the exact same output only at different scales - is present. So does that make the answer 'Yes'?

That 'fractal' property on its own is arguably enough to merit such an FSM being called a self emulator - but not a self interpreter. A self interpreter, at least for any sensible definition, has to have more oomph.

A null interpreter that interprets the language 'HALT' should not count as a self interpreter. The language has to have more complexity. In the above examples we're not asking the FSM to do enough. It's ignoring its inputs.
An interpreter that can interpret itself is only interesting because it could also interpret other programs that are written in the same language with minimal change (roughly speaking minimal change means changing only a pointer to point to a different program).

So now the problem. An FSM, and equally a pushdown automaton, cannot step backwards in its input tape. If we consider the input symbols on the tape as a program in a computer language then neither FSM nor pushdown automaton can qualify as an interpreter in the conventional sense.

Well, we did already know we can't interpret a language that is Turing complete using FSM or pushdown automaton. What about some more restrictive language that could, say, generate a repeating binary pattern of arbitrary length?

We allow three instructions,

OUT0 - outputs a 0
OUT1 - outputs a 1
RESTART - goes back to the beginning.

We can write an FSM for any program in this language. That really is quite easy. We cannot write one FSM that can interpret any program in this language.

The same is true for a pushdown automaton. Beyond a certain size of sequence it has to use the stack for memory. The problem is that as soon as it reads back from the stack the stack part of the pushdown automaton has forgotten what was there. Meanwhile the FSM part can only store a sequence of limited size.

A push down automaton and an FSM cannot interpret the simple three instruction language. If a fixed FSM or a pushdown automaton is able to execute arbitrary programs in some language, that language must be not only not Turing complete, it has to be simpler than the one given. That's so restrictive that it's legitimate to say that FSMs and pushdown automata cannot be self-interpreting.