Automata and Computability

A Programmer's Perspective

Ganesh Gopalakrishnan

• Publisher: Chapman and Hall/CRC
• Year: 2019
• ISBN:
  9781351374286
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

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.

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.¹ 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.²

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!”³

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).

Figure 1.1: Babbage’s Analytical Engine. By Science Museum London / Science and Society Picture Library. Reproduced under Creative Commons Attribution-Share Alike 2.0 Generic license. http://creativecommons.org/licenses/by-sa/2.0.

Figure 1.2: The website http://aturingmachine.com and the Youtube Video https://youtu.be/E3keLeMwfHY of a Mechanical Turing Machine by Mike Davey. Please search for An Interview with Mike Davey about his Homemade Turing machine also.

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 $a^n+b^n=c^n$ 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:⁴

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.⁵

For concreteness, Hilbert’s tenth problem was to devise an algorithm for finding solutions (over integers) for Diophantine equations—equations of the form

$3x^2-2xy-y^{2}z-7=0.$

Another Diophantine equation is

$x^2+y^2+1=0.$

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.⁶ 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”).⁷

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.⁸

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.⁹ See a modern Tur...