The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics (Oxford Landmark Science)

by Roger Penrose

variables that can occur in an expression. We regard the prime (‘) as a separate symbol of the formal system, so that the actual number of symbols remains finite. We shall

Hilbert’s hope was that for any string of symbols representing a mathematical proposition, say P, one should be able to prove either P or ~P, depending upon whether P is true or false. Here we must assume that the string is syntactically correct in its construction, where ‘syntactically correct’ essentially means ‘grammatically’ correct – i.e. satisfying all the notational rules of the formalism, such as brackets being paired off correctly, etc. – so that P has a well-defined true or false meaning. If Hilbert’s hope could be realized, this would even enable us to dispense with worrying about what the propositions mean altogether! P would just be a syntactically correct string of symbols.

The point of view that one can dispense with the meanings of mathematical statements, regarding them as nothing but strings of symbols in some formal mathematical system, is the mathematical standpoint of formalism.

would have to be false as an arithmetical proposition. Our formal system should not be so badly constructed that it actually allows false propositions to be proved! Thus, it must be the case that there is in fact no proof of Pk(k). But this is precisely what Pk(k) is trying to tell us. What Pk(k) asserts must therefore be a true statement, so Pk(k) must be true as an arithmetical proposition. We have found a true proposition which has no proof within the system! What about its negation ~Pk(k) It follows that we had also better not be able to find a proof of this either. We have just established that ~Pk(k) must be false (since Pk(k) is true), and we are not supposed to be able to prove false propositions within the system! Thus, neither Pk(k) nor ~Pk(k) is provable within our formal system. This establishes Gödel’s theorem.

Notice that something very remarkable has happened here. People often think of Gödel’s theorem as something negative -showing the necessary limitations of formalized mathematical reasoning. No matter how comprehensive we think we have been, there will always be some propositions which escape the net. But should the particular proposition Pk(k) worry us?

In a sense, no; but it leads us into some difficult mathematical considerations that cannot be gone into in detail here. The above procedure was discussed by Alan Turing in a paper4 in 1939. In fact, very remarkably, any true (but just universally quantified) proposition in arithmetic can be obtained by a repeated ‘Gödelization’ procedure of this type! See Feferman (1988).

This requires that our infinite family can be systematized in some algorithmic way. To be sure that such a systematization correctly does what it is supposed to do, we shall need to employ insights from outside the system – just as we did in order to see that Pk(k) was a true proposition in the first place. It is these insights that cannot be systematized – and, indeed, must lie outside any algorithmic action!

the meaning of the axiom system and rules of procedure, and convincing oneself that these indeed provide valid ways of arriving at mathematical truths, one may be able to code this insight into further true mathematical statements that were not deducible from those very axioms and rules. The derivation of the truth of Pk(k), as outlined above, depended upon such a principle.

Be that as it may, it seems to me that it is a clear consequence of the Gödel argument that the concept of mathematical truth cannot be encapsulated in any formalistic scheme. Mathematical truth is something that goes beyond mere formalism. This is perhaps clear even without Gödel’s theorem. For how are we to decide what axioms or

(This law is the basis of the mathematical procedure of ‘reductio ad absurdum’, cf. p. 78

deny this law. This is basically because they are taking a different attitude to the concept of existence, demanding that a definite (mental) construction be presented before it is accepted that a mathematical object actually exists. Thus, to an intuitionist, ‘existence’ means ‘constructive existence’.

I have briefly described the three main streams of present-day mathematical philosophy: formalism, Platonism, and intuitionism. I have made no secret of the fact that my sympathies lie strongly with the Platonistic view that mathematical truth is absolute, external, and eternal, and not based on man-made criteria; and that mathematical objects have a timeless existence of their own, not dependent on human society nor on particular physical objects. I have tried to make my case for this view in this section, in the previous section, and at the end of Chapter 3.

As it stands, this procedure does not so readily show that we have a Gödel proposition (like Pk(k)) that is true, but not provable within the system. However, if we recall the argument given in Chapter 2 on ‘how to outdo an algorithm’ (cf. p. 83), we shall see that we can do something very similar. In that argument we were able to show that, given any algorithm for deciding whether a Turing machine action stops, we can produce a Turing machine action that we see does not stop, yet the algorithm cannot. (Recall that we insisted that the algorithm must correctly inform us when a Turing machine action will stop though it can sometimes fail to tell us that the Turing machine action will not stop – by running on forever itself.) Thus, as with the situation with Gödel’s theorem above, we have a proposition that we can see, by the use of insight, must actually be true (not-stopping of the Turing machine action), but the given algorithmic action is not capable of telling us this.

We shall be concerned only with computability questions, namely: ‘Which kinds of sets of natural numbers can be generated by algorithms and which cannot?’

The definition of computability

propositions Q0, Q1, Q2, Q3,, . . . of the formal system will actually have proofs within the system. These ‘provable’ propositions will have numbers which constitute some set in ℕ in fact the set P of ‘theorems’ considered above. We have, in effect, already seen that there is an algorithm for generating, one after the other, all the propositions with proofs in some given formal system. (As outlined earlier, the ‘nth proof’ Πn is obtained algorithmically from n. All we have to do is look at the last line of the nth proof to find the ‘nth proposition provable within the system’, i.e. the nth ‘theorem’.) Thus we have an algorithm for generating the elements of P one after the other (perhaps with repetitions – that makes no difference).

There are many other subsets of ℕ which are recursively enumerable, and we need make no reference to our formal system in order to define them.

This again illustrates aspects of Gödel’s theorem: that the concept of mathematical truth is only partly accessible by the means of formal argument.

Intelligence, incidentally, is useful – although not necessary – also for establishing the existence of an ‘equality’.)

(This list is adapted from one given in 1955 by G. S. Tseitin and Dana Scott; see Gardner 1958, p. 144.) Thus this particular word problem by itself is an example of non-recursive mathematics, in the sense that using this particular initial list we cannot algorithmically decide whether or not two given words are ‘equal’.

the purposes of an illustration, that the Mandelbrot set is, in some appropriate sense, non-recursive. Since its complement is recursively enumerable, this would mean that the set itself would not be recursively enumerable. I think that it is likely that the form of the Mandelbrot set has some lessons to teach us as to the nature of non-recursive sets and non-recursive mathematics.

Penrose tiles’);

Look at penrose using his name to identify his tiles

However, there are various general things that are known, or conjectured, concerning certain absolute limitations on how much the speed of an algorithm can be increased.

‘Hamiltonian circuit’

To a formalist, the continuum hypothesis is ‘undecidable’ since it cannot be established or refuted using the standard (Zermelo–Frankel) formal system,

These are the broad areas of classical physics. What of quantum physics? Unlike relativity theory, quantum theory is beginning to have a really significant impact on technology. This is partly owing to the understandings that it has provided, in certain technologically important areas such as chemistry and metallurgy. Indeed, some would say that these areas have actually become subsumed into physics,

What about physical understandings of more recent origin? Some readers may have come across excitedly-expressed ideas, involving such names as ‘quarks’ (cf. p. 200), ‘GUT’ (Grand Unified Theories), the ‘inflationary scenario’ (see end-note 13 on p. 449), ‘supersymmetry’, ‘(super) string theory’, etc. How do such new schemes compare with those that I have just been referring to? Shall we need to know about them also? I believe that in order to put things in a more appropriate perspective, I should formulate three broad categories of basic physical theory. I label these as follows: 1. SUPERB, 2. USEFUL, 3. TENTATIVE.

The most ancient of the SUPERB theories is the Euclidean geometry that we learn something of at school. The ancients may not have regarded it as a physical theory at all, but that is indeed what it was: a sublime and superbly accurate theory of physical space – and of the geometry of rigid bodies. Why do I refer to Euclidean geometry as a physical theory rather than a branch of mathematics? Ironically, one of the clearest reasons for taking that view is that we now know that Euclidean geometry is not entirely accurate as a description of the physical space that we actually inhabit! Einstein’s general relativity now tells us that space(–time) is actually ‘curved’ (i.e. not exactly Euclidean) in the presence of a gravitational field. But that fact does not detract from Euclidean geometry’s characterization as SUPERB. Over a metre’s range, deviations from Euclidean flatness are tiny indeed, errors in treating the geometry as Euclidean amounting to less than the diameter of an atom of hydrogen!

In addition, it explains various detailed observational facts which are incompatible with the older Newtonian scheme. One of these (the ‘binary pulsar’, cf.

Newtonian binary pulsar replaced by einstein relativity

quantum chromodynamics,

He was able to provide criteria, stated in terms of integer operations, for deciding when one length ratio exceeds another, or whether the two are actually to be regarded as exactly equal. The idea was roughly as follows: If a, b, c, and d are four lengths, then a criterion for ascertaining that the ratio alb is greater than the ratio c/d is that there exist integers M and N such that a added to itself N times exceeds b added to itself M times, whilst also d added to itself M times exceeds c added to itself N times.* A corresponding criterion can be used to ascertain that a/b is less than c/d.

Part (but by no means all) of the reason for this was an absence of any sufficiently accurate means of keeping time, i.e. of a reasonably good ‘clock’. Such a clock is needed so that changes in position can be accurately timed, and so that the speeds and accelerations of bodies can be well ascertained. Thus, Galileo’s observation in 1583 that a pendulum could be used as a reliable means of keeping time had a far-reaching importance for him (and for the development of science as a whole!) since the timing of motion could then be made precise.4 Some fifty-five years later, with the publication of Galileo’s Discorsi in 1638, the new subject of dynamics was launched – and the transformation from ancient mysticism to modern science had begun!

Suppose that we adopt the rigid spherical ball picture, requiring that when two of the spheres collide they simply rebound perfectly elastically. That is to say, they separate again without any loss of energy (or of total momentum), as if they were perfect billiard balls. We also have to specify exactly how the forces are to act between one ball and another. For simplicity, we can assume that the force that each ball exerts on each other ball is along the line joining their centres, and its magnitude is a specified function of the length of this line. (For Newtonian gravity this assumption automatically holds true, by a remarkable theorem due to Newton; and for other laws of force it can be imposed as a consistent requirement.) Provided that the balls collide only in pairs, and no triple or higher-order collisions occur, then everything is well defined, and the outcome depends in a continuous way on the initial state (i.e. sufficiently tiny changes in the initial state lead to only small changes in the outcome). The behaviour of glancing collisions is continuous with the behaviour when the balls just miss one another. There is, however, a problem with what to do with triple or higher-order collisions. For example, if three balls A, B, and C come together at once, it makes a difference whether we consider A and B to come together just first, and C then to collide with B immediately afterwards, or whether we consider A and C to come together first, and B then to collide with...

Fig. 5.8. A triple collision. The resulting behaviour depends critically upon which particles come together first, so the outcome depends discontinuously on the input.

Let me first illustrate, with an admittedly absurdly artificial example, that computability and determinism are different, by exhibiting a ‘toy model universe’ which is deterministic but not computable.

A very tiny change in the initial data may rapidly give rise to an absolutely enormous change in the resulting behaviour. (Anyone who has tried to pocket a billiard ball, by hitting it with an intermediate ball that has to be hit first, will know what I mean!) This is particularly apparent when (successive) collisions are involved, but such instabilities in behaviour can also occur with Newtonian gravitational action at a distance (with more than two bodies). The term ‘chaos’, or ‘chaotic behaviour’ is often used for this type of instability. Chaotic behaviour is important, for example, with regard to the weather. Although the Newtonian equations governing the elements are well known, long-term weather prediction is notoriously unreliable!

The versatile and original Irish mathematician William Rowan Hamilton (1805–1865) – who was also responsible for the Hamiltonian circuits discussed on p. 185) – had developed this form of the theory in a way that emphasized an analogy with wave propagation. This hint of a relation between waves and particles – and the form of the Hamilton equations themselves–was highly important for the later development of quantum mechanics. I shall return to that aspect of things in the next chapter. One novel ingredient of the Hamiltonian scheme lies in the ‘variables’ that one uses in the description of a physical system. Up until now, the positions of particles were taken as primary, the velocities being simply the rate of change of position with respect to time. Recall (p. 217) that in the specification of the initial state of a Newtonian system we needed the positions and the velocities of all the particles in order that the subsequent behaviour be determinate. With the Hamiltonian formulation we must select the momenta of the particles rather than the velocities. (We noted on p. 214 that the momentum of a particle is just its velocity multiplied by its mass.) This might seem a small change in itself, but the important thing is that the position and momentum of each particle are to be treated as though they are independent quantities, more or less on an equal footing with one another. Thus one ‘pretends’, at first, that the momenta of the various particles have nothing to do with t...

Hamiltonian mechanics- Position and momenta

Try to imagine a ‘space’ of a large number of dimensions, one dimension for each of the coordinates x1, x2, . . ., p1, p2, . . . (Mathematical spaces often have many more than three dimensions.) This space is called phase space (see Fig. 5.10).

It would require infinite precision for the coordinates of a phase-space point – i.e. all the decimal places! – in order for it to make sense to say that the point is non-computable. (A number described by a finite decimal is always computable.)

We may ask, in view of this spreading throughout phase space, how is it possible at all to make predictions in classical mechanics? That is, indeed, a good question. What this spreading tells us is that, no matter how accurately we know the initial state of a system (within some reasonable limits), the uncertainties will tend to grow in time and our initial information may become almost useless. Classical mechanics is, in this kind of sense, essentially unpredictable. (Recall the concept of ‘chaos’ considered above.)

In relation to Hamiltonian Phase Spaces being incomputable in terms of the spread of particles in phase space, even though the volume of psrticles as positions and momenta are virtually unchanged.

How is it, then, that Newtonian dynamics has been seen to be so successful? In the case of celestial mechanics (i.e. the motion of heavenly bodies under gravity), the reasons seem to be, first, that one is concerned with a comparatively small number of coherent bodies (the sun, planets, and moons) which are greatly segregated with regard to mass – so that to a first approximation one can ignore the perturbing effect of the less massive bodies and treat the larger ones as just a few bodies acting under each other’s influence – and, second, that the dynamical laws that apply to the individual particles which constitute those bodies can be seen also to operate at the level of the bodies themselves – so that to a very good approximation, the sun, planets, and moons can themselves be actually treated as particles, and we do not have to worry about all the little detailed motions of the individual particles that actually compose these heavenly bodies!10 Again we get away with considering just a ‘few’ bodies, and the spread in phase space is not important.

The reason for classical mechanics success- Limited variance and simplicity. Though, I suppose the simplicity element is not so much related to its successful adaptation but rather it's prominence. As with any great pieces of art there is beauty in simplicity.

This spreading effect in phase space has another remarkable implication. It tells us, in effect, that classical mechanics cannot actually be true of our world! I am somewhat overstating this implication, but perhaps not greatly so.

quantum effects can prevent this phase-space spreading. This is an important issue to which we shall have to return later (see Chapters 8 and 9).

The fact that moving electric charges can give rise to magnetic forces caused some additional complication, but it did not disrupt the scheme as a whole. Numerous mathematicians and physicists (including Gauss) had proposed systems of equations for the effects of moving electric charges which had seemed to be satisfactory within the general Newtonian framework. The first scientist to have made a serious challenge to the ‘Newtonian’ picture seems to have been the great English experimentalist and theoretician Michael Faraday (1791–1867).

I'll Have to read about faraday sometime.

One implication of Maxwell’s equations was that electric and magnetic fields would indeed ‘push’ each other along through empty space. An oscillating magnetic field would give rise to an oscillating electric field (this was implied by Faraday’s experimental findings), and this oscillating electric field would, in turn, give rise to an oscillating magnetic field (by Maxwell’s theoretical inference), and this again would give rise to an electric field and so on. (See Figs 6.26, 6.27 on pp. 350 and 351 for detailed pictures of such waves.) Maxwell was able to calculate the speed that this effect would propagate through space – and he found that it would be the speed of light! Moreover these so-called electromagnetic waves would exhibit the interference and puzzling polarization properties of light that had long been known

However, Dirac’s solution led to some alarming conclusions. He found that in order for the behaviour of the particles and fields to be determined by their initial data, it is necessary that not only must each particle’s initial position and velocity be known but its initial acceleration must be known too (a somewhat anomalous situation in the context of standard dynamical theories). For most values of this initial acceleration the particle eventually behaves in a completely crazy way, spontaneously accelerating into the distance at a speed that very rapidly approaches the speed of light! These are Dirac’s ‘runaway solutions’, and they do not correspond to anything that actually happens in Nature. One must find a way of ruling out the runaway solutions by choosing the initial accelerations in just the right way. This can always be done, but only if one applies ‘foreknowledge’ – that is to say, one must specify the initial accelerations in a way that anticipates which solutions eventually become runaway solutions, and avoids them. This is not at all the way that initial data are to be specified in a standard deterministic physical problem. With conventional determinism those data can be given arbitrarily, unconstrained by any requirement that the future is to behave itself. Here, not only is the future completely determined by data that can be specified at one time in the past, but the very specification of those data is very precisely constrained by the requirement that the...

This will provide a very good picture, and it should not be hard to accept that in principle the ideas will extend, without much change, to the full four-dimensional situation. The thing to bear in mind about a space-time diagram is that each point in the picture represents an event – that is, a point in space at a single moment, a point having only an instantaneous existence. The entire diagram represents the whole of history, past, present, and future. A particle, since it persists with time, is represented not by a point but by a line, called the world-line of the particle. This world-line – straight if the particle moves uniformly and curved if it accelerates (i.e. non-uniformly) – describes the entire history of the particle’s existence. Fig. 5.16. A light cone in Minkowski’s space–time (with just two spatial dimensions), describing the history of the light flash of an explosion that takes place at the event O, the space–time origin.

How time is represented on a space time graph

Now, one of the features of relativity theory is that it is impossible for a material particle to travel faster than light (more about this later). All the material particles coming from the explosion must lag behind the light. This means, in space–time terms, that the world-lines of all the particles emitted in the explosion must lie inside the light cone.

These properties must hold generally at all points of the space–time. There is nothing special about the origin; the point O is no different from any other point. Thus there must be a light cone at every point of the space–time, with a significance the same as that for the light cone at the origin. The history of any light flash – or the world-lines of photons, if we prefer to use a particle description of the light – is always along the light cone at each point, whereas the history of any material particle must always be inside the light cone at each point. This is illustrated in Fig. 5.17. The family of light cones at all the points may be regarded as part of the Minkowskian geometry of space–time.

In three-dimensional Euclidean geometry, the distance r of a point from the origin, in terms of standard Cartesian coordinates, is given by r2 = x2 + y2 + z2. (See Fig. 5.18a. This is just the Pythagorean theorem – the two-dimensional case being perhaps more familiar.) In our three-dimensional Minkowskian geometry, the expression is formally very similar (Fig. 5.18b), the essential difference being that we now have two minus signs: Fig. 5.18. A comparison between the ‘distance’ measures in (a) Euclidean geometry and (b) Minkowskian geometry (where ‘distance’ means ‘time experienced’). s2 = t2 – (x/c)2 – (z/c)2. More correctly we should have four-dimensional Minkowskian geometry, of course, and the ‘distance’ expression is s2 = t2 – (x/c)2 – (y/c)2 – (z/c)2.

Wow, Pythagorean theorem from Euclidean geometry can be used in minkowskis time space equations for light cones.

In particular, the reader may be acquainted with what is called ‘the twin paradox’ of relativity: one twin brother remains on the earth, while the other makes a journey to a nearby star, travelling there and back at great speed, approaching that of light. Upon his return, it is found that the twins have aged differently, the traveller finding himself still youthful, while his stay-at-home brother is an old man. This is easily described in terms of Minkowski’s geometry – and one sees why, though a puzzling phenomenon, it is not actually a paradox. The world-line AC, represents the twin who stays at home while the traveller has a world-line composed of two segments AB and BC, these representing the outward and inward stages of the journey (see Fig. 5.19). The stay-at-home twin experiences a time measured by the Minkowski distance AC, while the traveller experiences a time given by the sum16 of the two Minkowski distances AB and BC. These times are not equal, but we find: Fig. 5.19. The so-called ‘twin paradox’ of special relativity is understood in terms of a Minkowskian triangle inequality. (The Euclidean case is also given, for comparison.) AC > AB + BC, showing that indeed the time experienced by the stay-at-home is greater than that of the traveller. The above inequality looks rather similar to the well-known triangle inequality of ordinary Euclidean geometry namely (A, B, and C being now three points in Euclidean space): AC < AB + BC, which asserts that the sum of two s...

This is mind blowing