3.3 THE DEFINITION OF ALGORITHM

Question 1

What is an algorithm?

Answer 1

Informally speaking, an algorithm is a collection of simple instructions for carrying out some task.

Question 2

In 1900, mathematician David Hilbert delivered a now-famous address at the International Congress of Mathematicians in Paris. In his lecture, he identified 23 mathematical problems and posed them as a challenge for the coming century. The tenth problem on his list ?

Answer 2

concerned algorithms.

Question 3

What is a polynomial ?

Answer 3

A polynomial is a sum of terms, where each term is a product of certain variables and a constant, called a coefficient.

Question 4

A root of a polynomial is ?

Answer 4

an assignment of values to its variables so that the value of the polynomial is 0.

Question 5

When did the definition of algorithms arrive?

Answer 5

The definition came in the 1936 papers of Alonzo Church and Alan Turing. Church used a notational system called the λ-calculus to define algorithms.

Question 6

What was the Church–Turing thesis?

Answer 6

Turing and Church both defined algorithms. This connection between the informal notion of algorithm and the precise definition has come to be called the Church–Turing thesis.