Review of the Perimeter Institute Lecture at the Bruce County Museum on May 14

The Bruce County Museum and the Perimeter Institute again hosted a provocative lecture on May 14 in Southampton on 'Big Screen DVD'.

This was one of the more interesting of the PI lectures.  The lecture "A Madman Dreams of Turing Machines" by Jana Levin PhD Mathematical Physics MIT and Professor at Barnard College of Columbia University was well attended. 

Professor Levin stated immediately that her book was at the nexus of a novel and history, which proved prophetic when she presented her findings. 

The lecture danced across and back a number of times between novel and fact.  Most of the time she was on the fact side.  She selected novel form after some thought rather than a dual bio of two gifted and strange men, who did not collaborate in their lifetimes, but knew each other's work. It was still not clear after her explanation, why she did so.  It gave her more freedom, but at the same time placed a burden on her to not stray too far.

Her lecture featured two of the giants of mathematics and logic Kurt Goedel and Alan Turing.  She wanted to chronicle their discoveries and by way of the title, their eccentricities.  The facts are well known, but she filled in the gaps by presenting them in historical context

Kurt Goedel

To no surprise her opening gambit centred around the startling work of the enigmatic Goedel and his curiosity about common paradoxes.  Great minds were much involved with the form and substance of language, be it natural or symbolic.

The idea was to flush out meaning from syntax and semantics in order to seek truth.  Dictionaries are full of inconsistencies and our human languages suffer from lack strict rules of combination.

These paradoxes have been known from antiquity.  For example, what is the meaning of  "This sentence is false."

Levin told us that Goedel was an admirer of Ludwig Wittgenstein and he moved in exclusive company in the Vienna Circle in the 1920s.  Coming to grips with truth and its nature was part of the Vienna Circle's preoccupation.  The relationship of language and thereby symbols with truth was at the core of their discussions.  For example, what implications can be drawn from the following paradox.

All Cretans are liars

I am a Cretan.

Is this a meaningless construction of language created by drawing from a dictionary and placing words in their proper syntax or does it hide a deep problem in the nature of truth and they way we think?

Goedel's work once understood by Levin, devastated Levin's sense of order as it did mine, when I studied it.  I have not met a person involved in science, logic or  mathematics who was not so moved.

His discovery produced a sense of loss on the one hand and caution on the other.  His work was beautiful, but it is hard to draw delight from it.  Some background is appropriate.

David Hilbert

In 1900 in Paris there was an international conference of mathematicians.  The leading light of this small and select world was David Hilbert of the University of Goettingen in Germany.  At that time and until Hitler laid waste to reason, it was the place to be and he was the light of the University.

Hilbert outlined 23 unsolved problems in Paris that he hoped would be put to rest by the best minds in the world over the next century.  Some of them still remain.  One of Hilbert's special ones, a foundational issue, fell to Goedel's amazing insight 31 years later.

The task that Hilbert outlined was to establish once and for all a solid basis for mathematical thought and by way of an added benefit, the basis for all thought.  This had been the elusive goal of natural philosophy from the time of Aristotle.  Again in 1928 at the University of Bologna, he challenged the mathematical community to establish the basis for all thought.

It was assumed that this would be forthcoming.  It was just a matter of time or so Hilbert thought.  At the Paris conference he as much as said... "Gentlemen get going on this!"

Some of the greatest minds in Europe and the world laboured over this task including Bertrand Russell and Alfred North Whitehead. to name two.

Then in 1931 a strange young man of 25 living in Austria astounded the world of logic and mathematics.  In an instant he elevated himself to exclusive fame.  What did he do?

What Godel did was once and for all time shatter the absolute connection between proof and truth!  Just think of that!

He  looked at the basis for all mathematics and science, the Queen of Mathematics ... the natural numbers or the common arithmetic of whole numbers. He made arithmetic "talk about itself!".  He changed the paradigm like this:

The sentence "This sentence is false" was changed to "This sentence is not provable" and he made arithmetic tell us that there are such statements and they are  not decidable. What was so withering about this discovery was that it extended to all thought and all axiomatic systems. (broadly speaking ... systems with rules of operation)

He showed that in any mathematical system that is based upon axioms sufficient to describe arithmetic there are statements that cannot be shown to be either true or false.

In proper form what he proved was:

"The  incompleteness theorem states that for any self-consistent recursive axiomatic system powerful enough to describe the arithmetic of the natural numbers (Peano arithmetic), there are true propositions about the naturals that cannot be proved from the axioms."

There is something strange going on in the far reaches of what's possible in human thought. That's the pity of it all and it has a relentless impact on any serious young student.

What this strangeness is can be elusive. Goedel by way of arithmetic showed and proved that any axiomatic system can have questions within its scope that cannot be answered to be true or false.  That is, they  remain "undecided" forever.

(next column)


What an awful conclusion and how devastating to the human mind.  You see he proved something about the limits of proof and thereby truth itself.

Sadder yet, you cannot tell exactly which problems are undecided. or not and hence the word undecided is the right word from start to finish.  Therefore, a scholar can labour a lifetime over a problem that cannot be answered by any dint of hard work or explosive insight.

Furthermore, he showed that such systems and in particular human thought fall within these bounds and have either undecided questions or they may be forever incomplete axiomatically.

The impact of Goedel's thoughts were subtle and far reaching.  He showed that systems that are consistent are in fact incomplete. 

Some systems can be complete, however, but they are not so interesting.  Tic Tac Toe is such a system.  It has rules of play (axioms)  So it contains no inherent contradictions.  The first player with a proper move always wins. 

Even Chess can be shown to be 'uninteresting' in a far more complicated way. There is a winning strategy for it, even though it cannot be computed  easily from every set position.  By clever rote power Big Blue defeated Garry Kasparov, World Chess Champion.

First grade arithmetic is infinitely more complicated than chess and endlessly interesting.

You'll notice that both Tic-Tak-Toe and Chess have axioms or rules of play that are consistent and complete.  Arithmetic is not so simple even though its basic rules are well known.  Of course stalemates in Chess do occur, but they are not produced in the course of a winning strategy and are not paradoxes.

So, you can have a good set of axioms that are consistent.  They don't contain any contradictions in and of themselves, but yet they are forever incomplete and may generate contradictions and inconsistencies as theorems and do have undecided questions.

In human thought this means that people can deliberate faithfully and well and yet certain areas of truth will always elude them.

If you keep adding axioms to help answer questions that arise, you may find solutions, but that's not very good and your 9th grade geometry teacher will not like it.  He/she will say... stick with Euclid's 5 axioms.

You see Euclid built all of plain geometry with 5 axioms and only used the 5th (parallel lines) in the 28th proposition. 

This 5th axiom bothered everyone.  It's the one about parallel lines and many thought that it was not necessary, but this was later proved to be wrong.  It is necessary for plane geometry, but of course not for other forms of geometry. 

For example, what is the meaning of parallel in spherical geometry?  So you see the truth of two lines being parallel and never meeting is subject to context.

Goedel's discovery so shook the mathematical, philosophical and scientific world, that it has not recovered and it never will.  Goedel told us that there are limits to human thought.  You can ask questions that don't have answers within the system and never will.

Personally Goedel was a tortured man who was socially inept.  He had few close friends.  Albert Einstein was one of them as they would take long walks together at the Princeton Institute for Advanced Study.

Goedel was a hypochondriac and was very worried about being poisoned.  After his wife's health failed and she could no longer feed him, he starved himself to death  That's a sad thing, but what a mind he had.


Alan Turing

The more well known of the two men was Alan Turing.  At least as of now he is well known.  When he was doing his research, he was just another Cambridge and Princeton educated PhD.

In the war he worked in cryptography and thereby was instrumental in the ultimate defeat of Hitler.  He and others cracked the thought to be impenetrable Enigma Code of the Germans.  They did it with a precursor to the modern computer.  It was a highly specialized early indicator of things to come.

Socially inept as was Goedel, he eventually committed suicide after being accused over time of being an overt homosexual.

His work plays on top of Goedel's in that he uses logic in the form of an algorithm to perform some determined task.  Before what we know as modern computers were born, he created a mind experiment machine of great simplicity. 

It read instructions from a tape fed into it and performed a set of instructions which when put in sequence performed an algorithm to fulfill computational and tasks of logic.

You can recognize some legacy in the modern PC to Turing machines.  The machine could not compete of course with the modern computer in speed and ease of use, but that's not what's important in the history of the insight of Turing.

What he did was to strip away any unnecessary things from computation and make what was left stand out as the 'essentials',  This is what mathematicians and logicians do.

Once stripped clean of non-essentials Turing could talk about the limits of computation or what is known now as an algorithmic process.  The theoretical work led to the modern Computer Science that is studied today all over the world.

Next Alan looked at what the limits of a Turing Machine would be?  He decided on a mind test. Suppose that the Machine had been programmed in such a way that it could answer questions... kind of a super Google, eh?

What would happen if we hid the machine away and had an impartial questioner ask it questions?  Would the questioner be able to decide between human intelligence and machine intelligence.  This was the birth of the modern science called 'Artificial Intelligence'

Turing supposed that the human brain could be viewed as a  tape coded with instructions and some registers that could be accessed and manipulated much like our brains store and interchange knowledge with the outside world.  This test of 'who is behind the curtain' is called the Turing Test.

Turing was trying to get at the question of whether machines as described could 'Think'.  He felt that ideas about self awareness were too hard to pin down and define and it was more useful to use the Turing Test to determine Artificial Intelligence.  It has proven to be a tough task and the debate goes on today.  It appears that a "super google" is possible.

We should not bet againt a  Turing's Test machine that will be able to fool the questioner in the future, but to date they have not been able to do so.  Turing thought this could be done by the year 2000.

Some machines like the Quantum Computers are not Turing Machines and research continues on their limits at the University of Waterloo. 

What is sure, however, is that the core discovery of Goedel prevails.  There is a difference between what is true and what can be proven to be true.