Just a few notes

So is the telephone industry going to sue skype?
It's NOT illegal. ?? No, because it's not an infringelment of anything.

Is burning a CD for a friend an infringement of copywrite?

What would happen if there were an open source file sharing system that nobody owned?

What about bittorrent? Which is decentralised. Is there a case there?

Week 3 - The Swinging Sixties

The 1960's
Some people thought Fortran wasn't sutiable to the kind of things that they wanted to do, so they began to develop other languages.
1945, Vannevar Bush (PhD, MIT, 1917). Thought up hypertext, using microfilm, called Memex, where any piece of information could be linked to any other piece.
"It is an enlarged, intimate supplement to his memory".
Memex was to search by association rather than by indexing.
Noone paid any attention to this for another 20 years.
Be had a lot of power and influence in Washington at the time.

In 1965 Doug Nelson coined the word hypertext.

But it really only came about in the 1990's.

Algol 60
Was designed after Fortran.
The Zurich conference was the first formal attempt to address the issue of portability (machine independence). This freed them to be creative, but made implementation difficult. And as it wasn't a US product, it never really took off in the US. Burrows took it up, but Algol ended up disappearing.

But it was important because of its influence on following languages.
It became the defacto standard for writing algorithms in papers etc.

Fortran wasn't specified, but Algol was specified by BNF.
Algol wasn't a company product, it had better loop constructs, and recursion.

Lisp
List Processing wasn't new, however only at the very low level. So lisp language was proposed

Packet Switching.
Interactive data communication in the 1960's was circuit switched, which wasted 90% of the bandwidth.
The idea is we can chop everything up in bits, and then chuck them into the system, and then they can all go their separate ways and they can be routed and find their way to their destination.

"Information Flow in Large Communication Networks."

Nobody actually believed it would work. Even the military ignored his proposal. But by the 1970's, all networks were using it, because it was very cost effective.

The military wanted something that could surviuve a nuclear blast but never actually took it up.
1969 - In UCLA, a military finded process sent the first packet between two computers, which would eventually become the internet. It was two graduate students.

Image based GUI
The name of the software was sketchpad.
It was a remarkable new way for people to interact with computers.

Architecture

I can go ahead and develop something remarkable later on. I don't have to do it now. Focus on your opportunties and earn enough to be able to support the remarkable stuff later on.

IBM System/360

IBM operating systems.
How do you manage all the jobs you have to do? At this time, programs were written on punch tape, and you feed it through the reader, and it reads the program, and just executes it, and spits out the result.
It was pretty inefficient. You can imagine! So there was this operating system that you could just keep feeding it jobs, and it would complete them as fast as it could, printing out the answers.
This led to the IBM operating system where jobs were loaded and unloaded automatically.
Fred Brooks managing the system. He's the guy who wrote "The Mythical Man Month". (Whicxh cost me a $45 library fine). This book was based on the issues that arose in the development of IBM/360.

Object-Oriented Programming.
Simula was designed for doing simulations. A superset of Algol 60 that included the concept of a class. OO was born, with virtual procedures, inheritance etc.

Of course, the Americans didn't take much notice of it, so for a decade or more it never took off. Later, Smalltalk 80 and C++ really made it popular.

Computational Complexity.
People were starting to talk about it, and Hartmanis and Stearns, at Cornell. What's this trade off between space and time in computing?
NP Completeness Non-deterministic polynomial time
NP Complete are problems which are not polynomial. They are problems that for large numbers you just cannot solve, because they just take too long.
Millions of hours have probably already been spent on trying to find algorithms for NP Complete problems. If we could prove that P = NP, then we could solve them, but many believe that P is not equal to NP.

Major Developments Before 1960

Developments in computing.
Long distance telephone signals needed to be amplified, and vacuum tubes were pretty bad at the job.
1945 AT&T decided to find a substitute for the vacuum tubes.
After a number of unsuccessful tries, tensions started in the team, and Shockley decided to go it alone.
On Dec 16, 1947, Bardeen and Brattain, without telling Shockley, build a point - contact transistor from strips of gold foil. Shockley built a better one and pushed them aside, and tried to patent it himself.

A transistor is a three terminal device, one can control electrical current between the two terminals by applying electric current to the third terminal.

Some say that Shockley put the Silicon in Silicon Valley. He hired a few people to Shockley Semiconductor in Palo Alto, but no one from Bell labs (full of brilliant people) would work for him.
Seems like everyone who ever worked for him ended up leaving (and forming companies like Fairchild and Intel).

Bardeen stayed at Bell labs, and died in 1991.

Shockley's company folded and he joined Stanford. He had notorious thinking on race, genetics and intelligence. He even suggested voluntary sterilisation for low IQ people. He died in disgrace, in 1989.

Integrated circuits.
The transistor and advances in solid state physics led to the development of an integrated circuit. Chips.
Kilby, in 1956, produced the first IC to prove that resistors and capacitors can exist on the same piece of material.
Texas instruments came up with the same idea though, at the same time.

Claude Shannon
Shannon is called "The Father of Information Theory".
His thesis was called 'the most important masters theses of the century!'.

He said that switching is like boolean algebra. So you can analyse any kind of circuit using boolean algebra. Everyone was terribly impressed.
He also finished a thesis under Vannevar Bush.

Shannon said
"How can we measure information?"
"What does information mean?"

How do you define and quantify information?

Shannon provided mathematical definition of information. Defined entropy. Defined how to measure information as if it was a physical quantity.

Information is related to the probability of something happening. If you find out that something happened that you didn't know happened, then that is a lot of information. Conversely, if you are sure something has happened, and someone tells you it has, then that isn't much information.

In information theory, the entropy equations in like E=Mc2.

You can afford to have a longer code when the uncertainty is higher, but a shorter code when you are more sure about what you're sending will be understood. This is how you minimise message length.

He died of Alzheimer's in 2001.

Artificial Intelligence.
Once again, a paper of Turing, written in 1950, dealing with the issue of whether machines can think. It detailed the Turing test.

Hashing
Appears to be developed in mid 1950s at IBM by Luhn. It arose from the problem of accessing information that is stored on disk. It's used in many database systems.

Fortran and it's compiler.
Before this, all programming had to be done in machine language!
It was the first high level language.

John Backus hated studying, and was thrown out of Uni. So he joined the Army.
But they sent him to study pre-med in Atlantic City, treating head wounds. He was found to have some tumor in his head himself. he quit medical school after just 9 months.
He moved to new york, and went to a radio technician school to learn to build a hi-fi unit. He enjoyed the teacher and work. He liked the fact that math had an application.
He did math at Columbia University, and joined IBM in 1950.

There he started developing Fortran, round about when Von Nuemann was getting sick of it and saying that we didn't even need a higher level programming and that programming wasn't even a problem.
One of the hardest problems was what the language would look like, and how would the computer translate (parse) it?
In 1959 he invented the Backus Naur Form (BNF).

Backus thought that FORTRAN and Algol weren't very good ways for humans to tell the computer what to do. His idea was that you should be able to tell the machine "This is what I want to be done". So he thought up the idea of functional programming. He defined all these languages that never took off though.
After FORTRAN, Algol and Lisp followed, and them more after that.
Algol had two major advantages over FORTRAN. The notion of local variables and that of recursion. Lisp was invented to help with AI work.
Algol was sort of designed, praised, but never took off.

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.