You all have varied mathematics backgrounds - but one thing is sure - you have all written an algorithm and you have all had to do proofs based on a set of axioms.
For this reason, alone, you should be familiar with Kurt Godel (1906-1978). Below is from here .
This ended a hundred years of attempts to establish axioms to put the whole of mathematics on an
axiomatic basis. One major attempt had been by Bertrand Russell with Principia Mathematica
(1910-13). Another was Hilbert's formalism which was dealt a severe blow by Godel's results. The
theorem did not destroy the fundamental idea of formalism, but it did demonstrate that any system
would have to be more comprehensive than that envisaged by Hilbert's.
Godel's results were a landmark in 20th-century mathematics, showing that mathematics is not a
finished object, as had been believed. It also implies that a computer can never be programmed to
answer all mathematical questions.
He is best known for his proof of Godel's Incompleteness Theorems. In 1931 he published these
results in Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme.
He proved fundamental results about axiomatic systems showing in any axiomatic mathematical
system there are propositions that cannot be proved or disproved within the axioms of the system. In
particular the consistency of the axioms cannot be proved.
(Another nice page on his accomplishments .)
In a sense, Hilbert's work of formalizing mathematics in 1900 looked at mathematics as a sort of game in which you manipulate symbols by fixed rules without thinking of any possible meaning the symbols could have. Bertrand Russell wrote, "Thus mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true."
Working only in formal systems, Hilbert (~1928) asked three questions in particular
He believed the answers would be 'yes'
There are true statements that a consistent formal system will not produce.
His proof was based on clever reasoning such as this example:
(The set of statements is incomplete because it cannot produce all true statements.)
alternatively said:
So we are lead to decidability. It would be nice if we could first ask if it is provable, and then we could set to the task of proving it.
A problem is undecidable if there is no algorithm that takes as input an instance of the problem and determines whether the answer to that instance is 'yes' or 'no'.
Important point: Decidability is only a problem for infinite sets (an infinity of instances). Why?
This is called the halting problem.
(It is an example of a problem that is NP-hard but not in NP-complete (class of problems that can be solved but only in exponential time).)
Decidability and completeness
What do we know so far?
Alan Turing (1912-1954))
Turing, Alan (1936), "On computable numbers, with an application to the Entscheidungsproblem," Proc. London Math. Society, 2(42), 230-265. (first computer not until 1942)
Note that the word "computer" as used in the quotation means the person that Turing is going to replace by a machine.
Why should we care? From Compared to What?: An Introduction to the Analysis of Algorithms, Gregory J.E. Rawlins, page 421
Suppose you are a programmer at Yoyodyne Propulsion Labs and your boss asks you to find an efficient algorithm to generate a routing of wires on a new chip they're developing. Of course, costs being what they are and the world being what it is, Yoyodyne wants a routing using the least amount of wire ...
So, you work on this problem and come up with a crude brute force algorithm - all the clever algorithm tricks you learned in previous chapters failed. you couldn't find a way to avoid testing large numbers of the possible combinations. Unfortunately, the chip has sixty-four pin connectors. Even though you manage to cut the cost of trying each combination of connections to one second, your algorithm takes 264 seconds to run. ... Even assuming a computer capable of testing a pin assignment in a billionth of a second, your program will still take roughly six hundred years to run.
What to do? Do you tell your boss you can't solve the problem? from Garey and Johnson You could get fired. Do you tell your boss that it is impossible to do better from Garey and Johnson , so there is not point firing you?... from Garey and Johnson
Programmers were put in exactly that position about forty years ago. The digital computer had finally been invented...unfortunately, nobody knew that some problems are computationally harder than others; some are so hard as to be unsolvable in practice. ...
Are some problems harder than others? If so, Which ones? How much harder are they? If they are a lot harder, what do we do?
(e.g., 2+2=5 should never be arrived at)
Godel's Incompleteness Theorem
This statement is a lie.
Proof would provide a contradiction.
There exist statements that are True but not
decidable from axioms.
Consider this idea with a machine doing a logic proof...never know if not finished or won't ever stop (if it is not provable it will keep looking).
Decidability
A problem is decidable if there is an algorithm that takes as input an instance of the problem and determines whether the answer to that instance is 'yes' or 'no'.
The Halting Problem
Example: There is no machine X that when given an arbitrary machine Y, can determine if machine Y will stop on input I.
What is way cool is that these folks were all considering what it means to be computable and there were no computers in existence
"This statement is unprovable"
If mathematics were inconsistent, then every assertion could be provable. Thus arithmetics must be either inconsistent, or incomplete.
Decidability: How do we know which statement are provable and which are not?
Is there a mechanical process which could answer?
At the age of 10 (note he was only 22 when finished his dissertation) he received a book Natural Wonders Every Child Should Know, by Edwin Brewster. This book, so he told his mother, "opened his eyes to science." It stated, "For, of course, the body is a machine. It is a vastly complex machine, many , many times more complicated than any machine ever made by hands; but still after all a machine."
"Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite....
"The behaviour of the computer at any moment is determined by the symbols which he is observing, and his 'state of mind' at that moment...
As primitive as Turing machines seem to be, attempts to strengthen them seem not to have any effect.
More specifically, machines which are these "attempts to strengthen" can always be "reduced" back to the original version
(e.g., extra tapes (more memory), extra heads (parallelism), etc.)
Any problem for which one can write an algorithm can be done on a turing machine.
