Finite automata have two traditional applications in computer science: modeling of finite-state systems and description of regular set of finite words. In the last few years, several new applications for finite-state automata have emerged, e. These applications use finite-state automata to describe regular sets of infinite words and trees. I will describe such applications and will argue that we need change the way we teach automata theory. Unable to display preview. Download preview PDF.
|Published (Last):||20 June 2011|
|PDF File Size:||16.96 Mb|
|ePub File Size:||14.31 Mb|
|Price:||Free* [*Free Regsitration Required]|
Is the history of computer science solely a history of progress? I don't think so. Judge for yourself by reading the present post in which I scrutinize the famous textbooks of John E.
Hopcroft and Jeffrey D. I start by comparing the following two quotes. The emphasis in each quote is mine. At a first glance, both quotes seem to contradict each other. And then I could rest my case: the history of computer science is indeed one of confusion. But, actually, I have taken each quote out of context. The first quote belongs to an introductory chapter on complexity theory where time and space bounds matter while the second quote appears in an informal chapter on Turing machines where the sole distinction of interest is one between decidability and undecidability.
In retrospect, then, both the book and the book bring the same message. So there seems to be no problem after all. But in the following paragraphs I shall argue that the message conveyed in and again in is questionable and that it has been scrutinized by other software scholars as well. So perhaps the history of computer science is a history of conflation after all . Judge for yourself My contention is that Turing machines are mathematical objects and computers are engineered artifacts.
The former can serve as mathematical models of the latter. Likewise, the latter can serve as engineered models i. However, in their Chapter 8, they also attempt to mathematically — albeit informally — demonstrate that a computer can simulate a Turing machine and that a Turing machine can simulate a computer.
All this in order to come to the following dubious result:. Thus, we can be confident that something not doable by a TM cannot be done by a real computer. I will argue that to make sense of all this, we need to be explicit about our modeling activities. Specifically, we should distinguish between two persons:.
For an elaborate distinction between an engineer and a scientist see my previous post. Coming back to Chapter 8 in Hopcroft et al. Fine with me, but then we are stepping away from a purely mathematical argument. Coming then to the simulation of a computer with a Turing machine cf.
Fine with me — and there really is no contradiction here, so don't get me wrong — but the choices made are clearly modeling choices so that the overall argument works out in the first place.
In a word, Hopcroft et al. Hopcroft et al. They are implicitly working with a particular mathematical model of a real computer, not with a real computer itself. The authors are thus definitely not backing up their following two claims:.
Note that the modeling in 1. Moreover, modeling implies idealizing: see e. In this regard, the authors incorrectly draw the following conclusion:. The previous statement only holds if the authors have demonstrated an isomorphism between Turing machines on the one hand and real computers on the other hand.
But they haven't. The isomorphism that they are considering only holds between Turing machines and their carefully crafted models of real computers.
Moreover, is it not possible that if we look inside a real computer and refrain from mapping our observations onto our favorite mathematical objects, that the computer is, in some sense, doing something for us that Turing machines do not do?
Only if we look at real computers with our traditional spectacles — in which partially computable functions are the preferred objects — can we equate the Turing machine with the computer in a traditional and rather weak sense.
There is more. My contention, in contrast, is to view a Turing machine as one possible mathematical model of a computer program. A finite state machine is yet another mathematical model of a computer program. I, however, view neither model to be better, for it all depends on the engineering task at hand. However, every now and then Hopcroft et al. Programs are sufficiently like Turing machines that the [above] observations [ Furthermore, Hopcroft et al.
In their own words:. It is not always unproductive, it all depends on the engineering task at hand. The authors stick to the Turing machine model and motivate their choice by explaining that computer memory can always be extended in practice:. If we run out of memory, the program can print a request for a human to dismount its disk, store it, and replace it by an empty disk. So, to make the undecidability proof work, the authors have decided to model a composite system: a real computer with a human being.
No-nonsense engineers, by contrast, will prefer to use a weaker model of computation and stick to the system at hand: a real computer and nothing more. Based on their motivations not to use finite state machines, I would opt for a linear bounded automaton and not a Turing machine. But, of course, if I do that then the much-wanted undecidability result does not hold for linear bounded automata have a decidable halting problem.
That, in short, explains why mainstream computer scientists heavily defend the Turing machine as the one and only viable model of computation in an average computability course. To get a more coherent view on what is going on, and how to fix it, I gladly refer to my latest book Turing Tales . In sum, critical readers who resist indoctrination become amused when reading Hopcroft et al. A much better dissemination strategy, I believe, is to remain solely in the mathematical realm of Turing machines or other — yet equivalent — mathematical objects when explaining undecidability to students, as exemplified by the textbooks of Martin Davis [3, 4].
A separate concern, then, is to discuss and debate how that mathematical impossibility result could — by means of a Turing complete model of computation — have bearing on the engineered artifacts that are being modeled.
The writings of Robert Floyd , Benjamin Pierce , and Joe Wells , just to give three names, show that undecidability most definitely has a practical role to play when used properly. A lot of the above remains controversial in mainstream computer science. I recommend consulting the many references provided in my book  and also the related — but not necessarily similar — writings of Peter Wegner [13, 14, 15], Carol Cleland [1, 2], Oron Shagrir [11, 12], and Edward A.
Lee  in order to get the bigger picture. Is the Church-Turing Thesis True? Minds and Machines , , Recipes, algorithms, and programs. Computability and Unsolvability. Davis, R. Sigal, and E. Morgan Kaufmann, second edition, Turing Tales. Lonely Scholar, Communications of the ACM , , Hopcroft, R.
Motwani, and J. Introduction to Automata Theory, Languages, and Computation. Hopcroft and J. Formal Languages and their Relation to Automata. Addison-Wesley, MIT Press, Bounded quantification is undecidable.
ACM Press, Effective computation by humans and machines. Shagrir and I. Physical Hypercomputation and the Church-Turing Thesis. Why interaction is more powerful than algorithms.
Communications of the ACM , 40 5 , Wegner and D. Computation beyond Turing machines. Communications of the ACM , 46 4 , Principles of problem solving. Communications of the ACM , 49 7 , Typability and type checking in System F are equivalent and undecidable.
Annals of Pure and Applied Logic , 98 , Skip to main content. Quotes from and I start by comparing the following two quotes. Later on in that same chapter from , the authors write Turing Machines and Computers My contention is that Turing machines are mathematical objects and computers are engineered artifacts.
Hopcroft and Ullman
We consider three different recent applications of finite automata. They are chosen to emphasize the diversified applicapity of the theory. Unable to display preview. Download preview PDF. Skip to main content.
Nontraditional applications of automata theory
Applications of Finite Automata