juola@bruno.cs.colorado.edu says:
Mike McNally responds:
While we're being picky, I'll point out that (unless I'm wrong of course) it's not really an NFA, but a non-deterministic Turing machine (an "NTM"?) that's the automaton at issue here.
That is correct. As a matter of fact, it's an easy theorem that an NFA has the same computing capacity as a DFA; it is not known whether this theorem holds for more powerful machines, and is in fact the heart of the P ?= NP conjecture.
The terms you are using are ambiguious. NTMs are no more powerful than deterministic TMs. They are possibly faster, but there are no languages that NTMs can recognise that deterministic TMs cannot recognise. It is hypothesized (though more or less unprovable) that there is no more powerful model of computation than Turing machines in the sense of what operations can be performed. Speed is again, as I noted, a different matter. Perry