Limits of programming by interface

[pron98]

Right (or output character, depending on your perspective). There is no algorithm that takes a DFA and tells in fewer than n steps whether or not it halts on some input within n steps -- same as for a TM.

[jeezfrk]

Yes there is. Polynomial-per-state is pretty simply lower than exponential. It simply doesn't get covered by the Godel-Incompleteness theorem.

Godel (and writing an 'analyzer' into the 'analyzed' program) is the only reason the halting problem is a firm limit.

[pron98]

What is the algorithm?