eBook - ePub
Automata and Computability
A Programmer's Perspective
Ganesh Gopalakrishnan
This is a test
Partager le livre
- 328 pages
- English
- ePUB (adapté aux mobiles)
- Disponible sur iOS et Android
eBook - ePub
Automata and Computability
A Programmer's Perspective
Ganesh Gopalakrishnan
DĂ©tails du livre
Aperçu du livre
Table des matiĂšres
Citations
Ă propos de ce livre
Automata and Computability is a class-tested textbook which provides a comprehensive and accessible introduction to the theory of automata and computation. The author uses illustrations, engaging examples, and historical remarks to make the material interesting and relevant for students. It incorporates modern/handy ideas, such as derivative-based parsing and a Lambda reducer showing the universality of Lambda calculus. The book also shows how to sculpt automata by making the regular language conversion pipeline available through a simple command interface. A Jupyter notebook will accompany the book to feature code, YouTube videos, and other supplements to assist instructors and students Features
- Uses illustrations, engaging examples, and historical remarks to make the material accessible
- Incorporates modern/handy ideas, such as derivative-based parsing and a Lambda reducer showing the universality of Lambda calculus
- Shows how to "sculpt" automata by making the regular language conversion pipeline available through simple command interface
- Uses a mini functional programming (FP) notation consisting of lambdas, maps, filters, and set comprehension (supported in Python) to convey math through PL constructs that are succinct and resemble math
- Provides all concepts are encoded in a compact Functional Programming code that will tesselate with Latex markup and Jupyter widgets in a document that will accompany the books. Students can run code effortlessly href="https://github.com/ganeshutah/Jove.git/"here.
Foire aux questions
Comment puis-je résilier mon abonnement ?
Il vous suffit de vous rendre dans la section compte dans paramĂštres et de cliquer sur « RĂ©silier lâabonnement ». Câest aussi simple que cela ! Une fois que vous aurez rĂ©siliĂ© votre abonnement, il restera actif pour le reste de la pĂ©riode pour laquelle vous avez payĂ©. DĂ©couvrez-en plus ici.
Puis-je / comment puis-je télécharger des livres ?
Pour le moment, tous nos livres en format ePub adaptĂ©s aux mobiles peuvent ĂȘtre tĂ©lĂ©chargĂ©s via lâapplication. La plupart de nos PDF sont Ă©galement disponibles en tĂ©lĂ©chargement et les autres seront tĂ©lĂ©chargeables trĂšs prochainement. DĂ©couvrez-en plus ici.
Quelle est la différence entre les formules tarifaires ?
Les deux abonnements vous donnent un accĂšs complet Ă la bibliothĂšque et Ă toutes les fonctionnalitĂ©s de Perlego. Les seules diffĂ©rences sont les tarifs ainsi que la pĂ©riode dâabonnement : avec lâabonnement annuel, vous Ă©conomiserez environ 30 % par rapport Ă 12 mois dâabonnement mensuel.
Quâest-ce que Perlego ?
Nous sommes un service dâabonnement Ă des ouvrages universitaires en ligne, oĂč vous pouvez accĂ©der Ă toute une bibliothĂšque pour un prix infĂ©rieur Ă celui dâun seul livre par mois. Avec plus dâun million de livres sur plus de 1 000 sujets, nous avons ce quâil vous faut ! DĂ©couvrez-en plus ici.
Prenez-vous en charge la synthÚse vocale ?
Recherchez le symbole Ăcouter sur votre prochain livre pour voir si vous pouvez lâĂ©couter. Lâoutil Ăcouter lit le texte Ă haute voix pour vous, en surlignant le passage qui est en cours de lecture. Vous pouvez le mettre sur pause, lâaccĂ©lĂ©rer ou le ralentir. DĂ©couvrez-en plus ici.
Est-ce que Automata and Computability est un PDF/ePUB en ligne ?
Oui, vous pouvez accĂ©der Ă Automata and Computability par Ganesh Gopalakrishnan en format PDF et/ou ePUB ainsi quâĂ dâautres livres populaires dans Computer Science et Computer Science General. Nous disposons de plus dâun million dâouvrages Ă dĂ©couvrir dans notre catalogue.
Informations
1
What Machines Think
Computers are everywhere and their power seldom ceases to amaze even those deeply embedded within the field! Computers seem to do (or be involved with) everything: from processing payroll to making telephone calls and even brushing our teeth (hiding within electric toothbrushes). They have also beaten humans at (the quiz show called) Jeopardy! One may therefore ask in all honesty: âcan computers do everything?!â
There are obviously things computers canât do.1 But what all can they do, and what does âcan doâ mean in the context of a machine? Remember that these questions were raised during the early part of the 20th century when actual computers werenât around; therefore, it isnât clear what answers flew around. It is quite possible that people relied on their immediate experiences to provide answersâmuch the same way as people imagined airplanes to be before the Wright brothers flew one.2
Coming back to the subject of computing, early computing successes were marvels of engineering. Blaise Pascal created an impressive machine around 1642 to assist his father with his work (Page 1). According to Wikipedia, Pascal conceived the idea while trying to help his father in his job as a tax collector. Pascalâs calculators could add and subtract two numbers directly and multiply and divide by repetition. About 200 years later, Babbage designed the Analytical Engine (trial design of 1837 shown in Figure 1.1). He even hired the first ever programmerâ-Ada Lovelaceâwho was introduced to Babbage when she was just 17 years of age, and got âhooked onto computing!â3
At the turn of the 20th century, people started pondering the question of the fundamental limits of computing. They began formulating this question in terms of the types of problems in mathematics and logic that can be âsolvedâ using a machine. It wasnât clear why there should be a fundamental limit to the power of computers. After all, authors such as Jules Verne were at this time writing science fiction pieces pertaining to going to the moon in spaceships (even before planes arrived).
1.1 Problems Without Algorithms
One can always state problems without knowing how to solve them. For instance, Fermat posed the problem of finding a, b, c that are natural numbers greater than 1 such that for n > 2. This problem remained open for over 300 years till 1995 when it was conclusively settled by Andrew Wiles in the negative: no such a, b, c can exist [46]. Until that year, one could have defined a procedure that could have searched for every possible a, b, c in a systematic way for a given n (say 3). For instance, the procedure could list all a, b, c that add up to 6, then list all a, b, c that add up to 7, etc., till such an a,b,c, were found that satisfied this equation. However, since 1995, thanks to the proof by Andrew Wiles of a theorem called Fermatâs last theorem, we know that this procedure would go on forever, not finding any a, b, c. In fact, we now have an algorithm: just print âimpossible to find such a, b, câ and halt.
In the same vein, people in the 20th century were in hot pursuit of algorithms for pretty much every problem that can be posed in mathematics! Most notable in this quest was a German mathematician named David Hilbert who challenged the mathematics and logic community with 23 problems pertaining to logic, mathematics and computability. One of Hilbertâs challenges was to prove the following:4
There should be an algorithmâa systematic and mechanical procedure that also terminates on any inputâto decide the truth of any logical statement in mathematics.
This was such a bold quest: Hilbert wanted any mathematical question to be algorithmically solved (always halt with âhere is the solutionâ or âyou canât have a solution.â) A long line of famous mathematicians and logicians that includes Gödel, Church, and Turing showed that this goal was impossible to realize! They showed that many mathematical systems are undecidable: there isnât an algorithm to decide the truth or falsity of statements made in them! They also showed that many logical systems are incomplete: there are logical systems that are so powerful that one cannot prove known truths in them.5
For concreteness, Hilbertâs tenth problem was to devise an algorithm for finding solutions (over integers) for Diophantine equationsâequations of the form
Another Diophantine equation is
It turns out that the former has the solution x = 1, y = 2, z = â2
while the latter has no solution.
A series of results developed in the 1940s through 1970 by Julia Robinson.6 The joint work by Yuri Matiyasevich, Julia Robinson, Martin Davis, and Hilary Putnam helped settle Hilbertâs 10th problem in the negative through the so-called MRDP theorem (see a nice historical account at [34]). Their work showed that alas, we cannot write a single computer program that always halts and either prints out the solution for such an equation (if one exists) or prints out that such a solution does not exist. A third possibility is to be admitted in case the equation has no solution: any such program must necessarily loop and never halt!
In this book, we shall be building some of the foundations toward appreciating all this momentous work. Some of the later chapters will also detail the topic of the fundamental limits of computing.
The vast majority of this book, however, discusses the serendipitous outcomes of these early pursuits seeking the fundamental limits of computing. In the end, these pursuits did help settle many open theoretical questions, but along the way, they spun off many fundamental ideas that form the bedrock of modern Computer Science. Fundamental developments in this young field are led by a brand new community of researchers who go by the name computer scientist (and not âmathematicianâ or âlogicianâ).7
1.2 How to Define a Computer?
Even to get started on Hilbertâs program, one had to clearly define âa computer.â Remarkably, within a few decades of the early 20th century, mathematicians managed to arrive at the definition of a computer (i. e., an ultimate computing device). This work was spearheaded by many famous scientists including Alan Turing of England as well as Alonzo Church, Emil Post, Stephen Kleene and John von Neumann of the United States.8
Alan Turingâs approach was to assume basic representations for numbers (in terms of 0âs and 1âs) and describe how one performs operations on numbers. His recipe for expressing an algorithm went something like this:
âą At each step of the algorithm, if a character c (say 0) is read under the Turing machine head (or âcursorâ), change the character to a different one (say 1). Then move the head one step left, one step right, or stay at the same spot. Then advance to the next step of the algorithm.
âą The algorithm is deemed to have halted when it reaches one of the previously selected âhalting steps.â In that case, the computation ends, leaving behind the contents of the tape as the final result.
It was soon shown that anything that is mechanically computable can be described in elementary terms such as this.9 See a modern Tur...