Maybe I don't understand Dror's answer, although it doesn't seem correct. I'm not sure what is meant by "f is a subroutine hardwired to the machine". The idea of reflection solves this problem.

Moreover, I'm not sure why there is a need to "call f", the f Spectator described is not a hardwired subroutine (for example, that wouldn't apply to DFA's which don't have subroutines), but a mathematically defined function, whose result is the machine itself - no computation of f ever need be done during the machine's execution. Rather f defines the machine (there is a fundamental difference).

Most curiously of all is that the conclusion drawn was that a machine with an infinite number of states (defined in such a manner) cannot exist. Although there is a study of infinite automata, and such a model is clearly definable. The question isn't whether there is such a thing as a machine with an infinite number of states, it is what that machine can and can't compute…

Here's an example where an "infinite DFA" (the name is contradictory, but hey) will accept a CFL, demonstrating that finite automata are not equivalent to infinite automata:

D(q_{2k}, 0) = q_{2k+2}

D(q_{2k}, 1) = q_{2k-1}

D(q_{2k+1}, 1) = q_{2k-1}

D(q_{2k+1}, 0) = q_{reject}

Special cases:

D(q_{1}, 0) = D(q_{1}, 1) = q_{reject}

D(q_{0}, 1) = q_{reject}

D(q_{reject}, 1) = D(q_{reject}, 0) = q_{reject}

Quite simply, the machine accepts the language {0^{n}1^{n} | n >= 0}, because starting at q_{0} every 0 increments the index by 2, and then when a 1 is encountered at say 2k, we move to 2k-1, and for every following 1 we decrement the index by 2, until arriving at q_{1} (an accept state, along with q_{0}). The rest are details to make sure that if we get too many 1's we move into a non-accept state (q_{reject}) and remain there, etc.