John Nash had a great deal of influence on computing without ever really being part of it all. Here we tell of some of the things he worked on and why they are important.

It is sad to reflect on the fact that the popular press is marking the passing of one of the last generalists of mathematics by referring to him as the "Beautiful Mind" man. It is true that his struggle with schizophrenia for the ten years from 1960 - 70 formed the story behind the Russell Crowe film "A Beautiful Mind",  but this is just a tiny fragment and the most personal part of the narrative. 

At another trivial level you might be tempted to refer to him as the man who invented the word "hacker". It is reported that he used the term during lectures and seminars at MIT as an insult and it caught on. 

So what is important about John Nash?

The best known is that he is responsible for is the eponymous Nash Equilibrium theory. This is an important idea in game theory, but one that is very subtle and difficult to get right. The explanation in the film "A Beautiful Mind" gets it wrong, even if it is entertaining. Nash equilibrium demands that each player adopts a strategy that they would not change, to get a bigger reward if they knew the the strategies of the other players and were sure that these would not change as a result of any change they might make. Notice that this is subtle because it is "self supporting" in that all of the players must not benefit from changing their strategy - not just one.  

The classic example is the Prisoners Dilemma. Two prisoners, A and B, are unable to communicate and each is told that if they betray the other they get a smaller sentence while the other spends a longer time in jail. Clearly it seems that the best course of action is for both to say silent, but in this case we do not have a Nash equilibrium because, for example, if A changed to betray while B stayed with silence then A would benefit - in this case changing strategy is a good thing.

The Nash equilibrium only comes about if both A and B defect. Now they both receive shorter sentences, but not as short as if they both kept silent - clearly this is not the best outcome possible. However, it is an equilibrium because if either alone considers changing to silence while the other stays with the betray strategy then the person who changes does worse. Clearly neither prisoner would change their strategy knowing that the other prisoner had opted to betray. 

Interestingly the example of a Nash equilibrium given in the film isn't and you can easily see why. 

A beautiful blond walks into a bar with four brunettes and four guys discuss their strategies. First they all think that going after the blond would be the best. Then the Nash character explains that if they do this then none of them is likely to succeed because of the competition and they wouldn't get a brunette either because they would be seen to be second choice. The Nash character then goes on to explain that their best strategy is to ignore the blond and they all get a reward of a sub-optimal brunette.

OK - ignoring the strange sexist morality of this tale - you can see that it isn't a Nash equilibrium because if any one of the four guys knows that the other three are going after the brunette then it makes sense to switch strategy to go after the blond. This is an interesting social situation, but a Nash equilibrium it isn't.

So the film gets it wrong. 

It also gets lots of other things wrong about his illness and early life. It also doesn't explain how important the idea of the Nash equilibrium is in the study of non-cooperative games. It is used in analyzing conflicts, evolution and economics. 

What else did John Nash work on?

He solved Hilbert's 19th problem relating to a type of differential equation. The problem is very technical, but essentially asks:

if the differential equation that you get from a variational problem is an elliptic partial differential equation with analytic coefficients is the solution analytic.

I told you it was technical, but variational problems are a way of formulating mechanics, quantum mechanics and relativity and many other subjects all via the idea of minimizing a function called the Lagrangian. What Hilbert's 19th problem asks is, if you have a well behaved variational problem will the result be analytic, i.e. "nice". Nash solved this in 1956, but discovered that another mathematician had just published a completely separate proof. It is speculated that had either mathematician got the proof on their own then they would have been awarded the Fields medal for it. 

The Hilbert 19th problem is a sort of a result in computational complexity theory - you can't get a more complex result as a solution to a particular class of equations.  At about the same time he wrote a letter to the NSA which proposed an encryption system based on computational complexity. He proposed the idea that the true security of a cryptographic system depended on the difficulty of extracting the key from the cypher text. Today we think of this as a one-way or trap-door function - easy to compute but difficult to invert. Nash's letter contains the basic ideas of modern cryptography which took another 20 years to work out - but the NSA rejected it.

There are many more things to say about what Nash worked on. He produces some interesting but mostly neglected results on both quantum theory and relativity. However before closing it is fitting to mention another important result that Nash is reasonably well known for - his embedding theorems.

If you have a description of a very general n dimensional curved space - a Riemann manifold - then the question that arises is can all such curved spaces be embedded in a flat space of higher dimension? For example the surface of a sphere is a 2D curved space but it is obviously embeddable in 3D Euclidean i.e. flat space. Are all curved spaces, no matter how high their dimension or how odd their curvature and topology is, embeddable in a higher dimensional flat space? The answer is given by the Nash embedding theorems and it is yes. The theorems actually say that the embedding is isometric i.e. it preserves distances between all points. 

You can think of this as saying that curved spaces are just curved objects in a higher dimensional flat space and flat spaces are much easier to work with. These ideas were once just theoretical but today they have an importance in data analysis - embed a set of points in a high dimensional space and proceed to reduce the dimension with minimum distortion and in computer graphics where curved meshes can be worked on in a flat space. 

If John Nash had not had a problem with schizophrenia then the popular media would not be calling him the "beautiful mind" man and he would be less well known, but we might have more important results of the kind he produced in his lucid times. 

John Nash was awarded the Nobel Prize in Economics in 1994 and this year he, together with Louis Nirenberg, received the 2015 Abel Prize
"for striking and seminal contributions to the theory of nonlinear partial differential equations and its applications to geometric analysis."  

It was on  their way home after a week of celebrations in Norway where King Harald V had made the Abel Prize presentation that John Nash and his wife died in a traffic accident. According to CNN:

"Nash, 86, and Alicia Nash, 82, were riding in a taxi near Monroe Township when the incident occurred, State Police Sgt. 1st Class Gregory Williams said:

They were traveling southbound in the left lane when the taxi went out of control while trying to pass another car. The car crashed into the guard rail, and they were ejected from the vehicle. They were pronounced dead at the scene. 

John Nash should be an inspiration to all deep thinkers who don't want to be pigeon-holed into a single academic subject. In the the footnote to a paper he presented on general relativity (An Interesting Equation) he stated:

"Since this lecture is concerned with a topic that does not involve studies lying within the areas of the speaker’s greatest recognized professional expertise and since it is considered as “of interest” (but not necessarily of permanent value (when the future judges)) it seems appropriate not to fill the hour simply with a lecture presentation but instead to save some time during which questions and answers or suggestions and debate may occur."

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

 <ASIN:0691095272>

<ASIN:1451628420>

<ASIN:0309101921>