[quoting Hiddink, 18 May 99] In essence, all computer programs can be reduced to finite state automata.
Only in retrospect.
When I was a Computer Science student, we had to read a book by Sudkamp (Languages and Machines) in which there was a theoretical proof that computers based on the Neumann model (central processing unit and a memory with instructions) can be translated into Turing machines. A Turing machine is a finite state machine.
Turing machines are not finite. There are four levels of problems or "languages" which can be computed. Turing machines can compute the highest level. Finite state automata compute only the lowest. Given a string ABA and a rule "Replace B with ABA" we can generate AABAA, or AAABAAA, etc. A finite state automaton cannot compute this language.
But this is not important. My point is that, in spite of attempts to make CBI complex, the discourse essentially reduces to action-response, action-response, action-response. This is not like my conversation with you, which has a history, is interrupted with conversations with other people which both of us remember, and which contains conversations within conversations (i.e., AABAA). I don't think we need to emulate human discourse perfectly, but we need to think about the relative "naturalness" of our interfaces. Do they allow us to do what humans usually want to do? Or does this matter?