Godel, Turing and Von Neumann
Godel, Turing and Von Neumann. Three European born geniuses who all ended up a bit nutty, and spent a bit of time at Princeton. Today's lecture goes through their histories and what they contributed to the development of Computers, and in the case of Von Neumann, some other terrible technologies.
--
What has been reeeaallly important in computing?
The Major developments 1930-60 (list)
In the 50's, the transistor was developed, but it really took up to 1960's before they really came about.
Turing in the 50s was thinking about how to do things in an intelligent way.
Hashing - how do you compute the information in an efficient way? How do you find it?
Information theory about measuring information. Shannon theory
Because of the motivation of war, the motivation came about to build these computers to calculate missile trajectories quickly. Many people were working on building computers all over the world. Even in Sydney, and we were right up there, until the government decided that computers wouldn't be that useful.
Anyway, onto looking at the three fathers of modern computing.
Godel, Turing, Von Neumann. The three most brilliant Computer Scientists. They were geniuses!
Kurt Godel 1906 - 1978
Was working in Austria, but ended up in Princeton, with Einstein.
Born in 1906 in what was Austria-Hungary at the time.
Completeness and Consistency.
If you had some very basic rules of math, then from these rules, you could derive everything else.
The matter was that every mathematician was thinking about these three rules.
The intellectual basis of computing came from these mathematicians.
When Godel was 22, he attended one of Hilbert's lectures, and by the age of 25, he had proved incompleteness. Of course no one paid any attention to him!
There are only a few people who can follow the whole proof.
However, it ended a hundred years of attempts to establish axioms which would put the whole of mathematics on an axiomatic bases. It was a real blow to those who were discussing it!
So, now we know. Some things just can't be proved. They just can't. Is P = NP? That's a very recent one.
Conjectures (see wikipedia for a list of them). They may SEEM to be so, but we can't prove that they are. As you can see, there are many open problems.
When Hitler came to power, in 1933. Godel had little interest in politics, so in 1934 he gave a lecture "On undecidable propositions of formal mathematical systems"
Of course, Hitler was doing his thing in Europe, and Austria became part of Germany. Godel carried on. He lectured again at Princeton and Notre Dame in 38-39.
One day, he was beaten up because he was thought to be Jewish (he wasn't though). He was always a sickly person, and wasn't very fit, but he didn't want to be conscripted by the German army and managed to get a visa to the U.S.A via Russia and Japan. He would wear coats in Winter, and leave all the windows open in Winter because he was fearful of conspirators coming in and gassing him. He was distrustful of doctors. Because he feared being poisoned he only ate his wife's food, and when she became ill he decided not to eat, and essentially starved himself to death.
Alan Turing 1912 - 1952
Upper Middle Class British parents. Father was an Indian Civil servant.
Turing felt first at home in Kings College in Cambridge, and loved the intellectual life.
Somehow he heard about Hilbert and Godel, and became interested in logic.
He reformulated Godel's theorems, and thought about how it could be applied to computing. So by the age of 24, he published the paper in how similar things could be applied to computing.
The turing Machine.
Idealised computing device consisting of read/write head with a paper tape through it.
You inscribe on the tape before starting. The head is for I/O and reading writing symbols.
There are just 6 types of fundamental operations that a Turing machine can run
Each transition rule is a 4 tuple.
Any complex program can be represented by this machine. It might take billions of operations, but it can be done.
So the 1936 paper defined computation. If you can't put the problem on the tape, then you can't compute it. It put the absolute limit on what computers could achieve.
If you want to build a program that will tell you whether another program will stop. You can't do it. You can't ask another program whether this program will stop. This means he's proved the halting problem is unsolvable.
1935 - 45.
He returned to Britain, and cracked the German Enigma, but it was all top secret, so he never got the credit for the work he did.
Then he went to NPL and started development on the Automatic Computing Engine (ACE), because of delays, he went back to Cambridge, and began working on a chess program for a computer that did not exist. ACE was finished in 1950. We went to Uni of Manchester.
It's pretty amazing that Turing came up with the idea of computers even before there were any computers. He was just imagining at what a computer might be capable of.
What could a computer do if you had one?
His ideas led the field, but without credit, he was frustrated and took up Marathon running, and almost qualified for the 1948 Olympic games.
He returned to theoretical computing and thought that if a computer could fool a human it would be intelligent.
He was caught having an affair with a young man, and, because of his sexuality, he was given oestrogen injections to negate his sexual drive, and ended up committing suicide with a cyanide injected apple.
John Von Nuemann 1903 - 57
Born in Hungary
Pioneer of the modern digital computer. Worked out key steps to developing nuclear weapons, and then compaigned that it never be used or made because of how dreadful they are.
Von Neumann's record in math got him a place at Uni, but he never went to classes. They were boring!
Von Neumann was everywhere! Lecturing everywhere.
1929, Princeton invited him, and then he got married and went, and at the age of 28 in 1931 he was a professor at Princeton. Remember Einstein and Godel were there, and they paid him well.
He knew about many disciplines, from Physics, Mathematics, and Economics.
The most famous (infamous) application of his work was the detonation of the bombs in Japan, he personally computer the altitude that they should be detonated so that they caused the maximum amount of damage, because he was determined to keep America safe.
ENIAC
Presently, there were a few problems, the main being that a program couldn't be run on any other computer than that which it was written for. So Fortran and its compiler came about. By the time it was finished, people could no longer write code in machine language that was more efficient than the compiler. (It was a bit buggy at first).
Von Neumann joined the team in 45. The stored program concept was born. This was the most important development of computing. Store the program in memory itself, and then you can have much more control of what is going on. There was some conflict about who's idea it actually was.
He contributed to computer science in many other ways too, including merge sort. But I still think his name is a bit sullied by this whole violent political agenda and the application of his genius to it.
His political ideology was self described as "violently anti-communist, and much more militaristic than the norm". He favored preventative attack on the USSR, and had radical ideas like colouring the ice caps to control the weather.
Ironically he died of bone cancer possibly derived from the exposure to radiation from nuclear tests at Bikini atoll.
--
What has been reeeaallly important in computing?
The Major developments 1930-60 (list)
In the 50's, the transistor was developed, but it really took up to 1960's before they really came about.
Turing in the 50s was thinking about how to do things in an intelligent way.
Hashing - how do you compute the information in an efficient way? How do you find it?
Information theory about measuring information. Shannon theory
Because of the motivation of war, the motivation came about to build these computers to calculate missile trajectories quickly. Many people were working on building computers all over the world. Even in Sydney, and we were right up there, until the government decided that computers wouldn't be that useful.
Anyway, onto looking at the three fathers of modern computing.
Godel, Turing, Von Neumann. The three most brilliant Computer Scientists. They were geniuses!
Kurt Godel 1906 - 1978
Was working in Austria, but ended up in Princeton, with Einstein.
Born in 1906 in what was Austria-Hungary at the time.
Completeness and Consistency.
If you had some very basic rules of math, then from these rules, you could derive everything else.
The matter was that every mathematician was thinking about these three rules.
The intellectual basis of computing came from these mathematicians.
When Godel was 22, he attended one of Hilbert's lectures, and by the age of 25, he had proved incompleteness. Of course no one paid any attention to him!
There are only a few people who can follow the whole proof.
However, it ended a hundred years of attempts to establish axioms which would put the whole of mathematics on an axiomatic bases. It was a real blow to those who were discussing it!
So, now we know. Some things just can't be proved. They just can't. Is P = NP? That's a very recent one.
Conjectures (see wikipedia for a list of them). They may SEEM to be so, but we can't prove that they are. As you can see, there are many open problems.
When Hitler came to power, in 1933. Godel had little interest in politics, so in 1934 he gave a lecture "On undecidable propositions of formal mathematical systems"
Of course, Hitler was doing his thing in Europe, and Austria became part of Germany. Godel carried on. He lectured again at Princeton and Notre Dame in 38-39.
One day, he was beaten up because he was thought to be Jewish (he wasn't though). He was always a sickly person, and wasn't very fit, but he didn't want to be conscripted by the German army and managed to get a visa to the U.S.A via Russia and Japan. He would wear coats in Winter, and leave all the windows open in Winter because he was fearful of conspirators coming in and gassing him. He was distrustful of doctors. Because he feared being poisoned he only ate his wife's food, and when she became ill he decided not to eat, and essentially starved himself to death.
Alan Turing 1912 - 1952
Upper Middle Class British parents. Father was an Indian Civil servant.
Turing felt first at home in Kings College in Cambridge, and loved the intellectual life.
Somehow he heard about Hilbert and Godel, and became interested in logic.
He reformulated Godel's theorems, and thought about how it could be applied to computing. So by the age of 24, he published the paper in how similar things could be applied to computing.
The turing Machine.
Idealised computing device consisting of read/write head with a paper tape through it.
You inscribe on the tape before starting. The head is for I/O and reading writing symbols.
There are just 6 types of fundamental operations that a Turing machine can run
Each transition rule is a 4 tuple.
Any complex program can be represented by this machine. It might take billions of operations, but it can be done.
So the 1936 paper defined computation. If you can't put the problem on the tape, then you can't compute it. It put the absolute limit on what computers could achieve.
If you want to build a program that will tell you whether another program will stop. You can't do it. You can't ask another program whether this program will stop. This means he's proved the halting problem is unsolvable.
1935 - 45.
He returned to Britain, and cracked the German Enigma, but it was all top secret, so he never got the credit for the work he did.
Then he went to NPL and started development on the Automatic Computing Engine (ACE), because of delays, he went back to Cambridge, and began working on a chess program for a computer that did not exist. ACE was finished in 1950. We went to Uni of Manchester.
It's pretty amazing that Turing came up with the idea of computers even before there were any computers. He was just imagining at what a computer might be capable of.
What could a computer do if you had one?
His ideas led the field, but without credit, he was frustrated and took up Marathon running, and almost qualified for the 1948 Olympic games.
He returned to theoretical computing and thought that if a computer could fool a human it would be intelligent.
He was caught having an affair with a young man, and, because of his sexuality, he was given oestrogen injections to negate his sexual drive, and ended up committing suicide with a cyanide injected apple.
John Von Nuemann 1903 - 57
Born in Hungary
Pioneer of the modern digital computer. Worked out key steps to developing nuclear weapons, and then compaigned that it never be used or made because of how dreadful they are.
Von Neumann's record in math got him a place at Uni, but he never went to classes. They were boring!
Von Neumann was everywhere! Lecturing everywhere.
1929, Princeton invited him, and then he got married and went, and at the age of 28 in 1931 he was a professor at Princeton. Remember Einstein and Godel were there, and they paid him well.
He knew about many disciplines, from Physics, Mathematics, and Economics.
The most famous (infamous) application of his work was the detonation of the bombs in Japan, he personally computer the altitude that they should be detonated so that they caused the maximum amount of damage, because he was determined to keep America safe.
ENIAC
Presently, there were a few problems, the main being that a program couldn't be run on any other computer than that which it was written for. So Fortran and its compiler came about. By the time it was finished, people could no longer write code in machine language that was more efficient than the compiler. (It was a bit buggy at first).
Von Neumann joined the team in 45. The stored program concept was born. This was the most important development of computing. Store the program in memory itself, and then you can have much more control of what is going on. There was some conflict about who's idea it actually was.
He contributed to computer science in many other ways too, including merge sort. But I still think his name is a bit sullied by this whole violent political agenda and the application of his genius to it.
His political ideology was self described as "violently anti-communist, and much more militaristic than the norm". He favored preventative attack on the USSR, and had radical ideas like colouring the ice caps to control the weather.
Ironically he died of bone cancer possibly derived from the exposure to radiation from nuclear tests at Bikini atoll.
posted by Mathieu at 4:02 PM
0 Comments:
Post a Comment
<< Home