CS701 Handouts 2023

This is the first “pure” course in theoretical computer science. Be concerned with the following basic questions in computer

Q1. What is a computation?

Q2. Is there a universal model of computation?

Q3. Can everything be computed?

Q4. Is there a relation between computations and mathematics?

Q5. Can we identify problems that are not computable?

Q6. What resources are needed to perform a certain computation?

Q7. Can we identify computationally hard problems?

Earliest Models of Computation

In 30 seconds draw the earliest model of computation that comes to you mind. I think there were two earliest computers. Let me show you the pictures of these models that I have made.

Yes, I think computing as old as human beings. In fact, the earliest known mathematical artifact is the Lebombo bone which dates back to 35,000 BC! After that humans also used clay. Tablets which are found in many civilizations.

Abacus was the next device. Here is a picture of a typical abacus. Slide rule was another device that was invented in 1600‟s.

1. Tally sticks like the Lebombo bone are the earliest computing devices. Earliest known is 35,000 BC.
2. Clay tablets were then used to store the count of livestock etc.
3. Abacus is known to exist 1000 BC and 500 BC in Mesopotamia and China.
4. Around 1620 John Napier introduced the concept of logarithms. The slide rule was invented shortly afterwards.

CareerSee

More than physical devices we are interested in the history of concepts in computing. We are interested in very basic questions. Let us ask the following more important questions.

When was the first algorithm devised? This is a very difficult question. Since, algorithms were not studied the way we do them today.

Earliest Algorithms

Perhaps, the first algorithm devised was unary addition thousands of years ago in some cave. The limbobo bone type devices were used to execute that algorithm. The concept of an algorithm is very well developed in Euclid‟s school. Two striking examples are:

The Euclidean Algorithm to compute the GCD. It is a non-trivial algorithm, in the sense that it is not clear at all why it computes the GCD. The constructions by ruler can compass are examples of precise algorithms. The elementary steps are well defined and the tasks are well defined.

The most important question in theory of computation is: What is a computation? What is an algorithm? When was this question asked?

1900 International Congress of Mathematicians

In David Hilbert and eminent mathematician was invited to give a lecture at the international congress of mathematicians. In his talk he posed 21 questions as a challenge to 20th century mathematicians. His problems spanned several areas from mathematical analysis, logic, foundation of set theory and geometry. However, one of the question the 10th problem was very interesting

Hilbert’s Tenth Problem

Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

Note two important words:

1. Process
2. in a finite number of operations

Hilbert was asking for an algorithm!!

Let us look examine Hilbert‟s 10th question in modern language. Consider a polynomial in many variables for example:

X2 + y2 = 0 X2 + y2 = z2 ax + by + z3 + 17d3 = 14567

CareerSee

These are called diophantine equations. What we want to do is to ask if there is a solution in positive integers. For example X2 + y2 = z2 has a solution x = 3, y = 4 and z = 5. So this equation has a solution. On the other hand x2 + x +2y =39 does not have a solution. So the question is: Given a diophantine equation does it have a solution?

Hilbert‟s Tenth Problem was the following problem in computer science: Can we write a program that will take a diophantine equation as an input and tell us if the equation has solution in positive integers? He was asking for an algorithm.

A solution to Hilbert‟s tenth problem would mean that mathematicians could solve diophantine equations mechanically. It took almost 70 years to solve this question. Eventually Yuri Matiyasevich was able to solve Hilbert‟s Tenth Problem. What was Matiyasevich‟s solution? Did he invent an algorithm? No.

Matiyasevich‟s proved that Hilbert‟s 10th problem was unsolvable. There is no algorithm that can tell if a diophantine equation has solutions in positive integers. Note that to understand what he did is not easy. Matiyasevich did not say he is not smart enough to find a solution. He proved that no such algorithm existed. He was showing impossibility of the existence of an algorithm.

Impossibility Proofs

Impossibility proofs are not very uncommon in mathematics. Let us look at some of them: It is impossible to write as a ratio of two integers. It is impossible to trisect an angle with a straight edge and compass. It is impossible to cut a regular tetrahedron and put the pieces together into a cube of equal volume. (Here cuts are one that can be given with a hyperplane).

Matiyasevich‟s theorem belongs to this general class of theorems. But, it is of utmost importance for us since it talks about impossibility of the existence of algorithms.

In order to prove that algorithm cannot exist we must have a exact and mathematically precise definition of an algorithm. This is what is needed in order to show that an algorithm does not exist. Once a precise definition of an algorithm is given we can argue mathematically about them.

Turing Machines and Algorithms

Luckily the mathematical notion of what an algorithm and computation is was already developed for Mataysavich. Let us ask the most fundamental question in theory of computation. What is an algorithm? What is a computation?

The seeds of answer to this question were also sown by Hilbert. In 1928, Hilbert who wanted to systematize all of mathematics had posed the Entscheidungs problem. He wanted an algorithm that would take a mathematical assertion and would decide if the assertion was true or not!!!! That would be an amazing algorithm (if it existed). In 1936, Alan Turing, Alonzo Church showed that the Entscheidungs problem was unsolvable.