Complexity and Prediction Part V: The crisis of mathematical paradoxes, Gödel, Turing and the basis of computing

Before the referendum I started a series of blogs and notes exploring the themes of complexity and prediction. This was part of a project with two main aims: first, to sketch a new approach to education and training in general but particularly for those who go on to make important decisions in political institutions and, second, to suggest a new approach to political priorities in which progress with education and science becomes a central focus for the British state. The two are entangled: progress with each will hopefully encourage progress with the other.

I was working on this paper when I suddenly got sidetracked by the referendum and have just looked at it again for the first time in about two years.

The paper concerns a fascinating episode in the history of ideas that saw the most esoteric and unpractical field, mathematical logic, spawn a revolutionary technology, the modern computer. NB. a great lesson to science funders: it’s a great mistake to cut funding on theory and assume that you’ll get more bang for buck from ‘applications’.

Apart from its inherent fascination, knowing something of the history is helpful for anybody interested in the state-of-the-art in predicting complex systems which involves the intersection between different fields including: maths, computer science, economics, cognitive science, and artificial intelligence. The books on it are either technical, and therefore inaccessible to ~100% of the population, or non-chronological so it is impossible for someone like me to get a clear picture of how the story unfolded.

Further, there are few if any very deep ideas in maths or science that are so misunderstood and abused as Gödel’s results. As Alan Sokal, author of the brilliant hoax exposing post-modernist academics, said, ‘Gödel’s theorem is an inexhaustible source of intellectual abuses.’ I have tried to make clear some of these using the best book available by Franzen, which explains why almost everything you read about it is wrong. If even Stephen Hawking can cock it up, the rest of us should be particularly careful.

I sketched these notes as I tried to pull together the story from many different books. I hope they are useful particularly for some 15-25 year-olds who like chronological accounts about ideas. I tried to put the notes together in the way that I wish I had been able to read at that age. I tried hard to eliminate errors but they are inevitable given how far I am from being competent to write about such things. I wish someone who is competent would do it properly. It would take time I don’t now have to go through and finish it the way I originally intended to so I will just post it as it was 2 years ago when I got calls saying ‘about this referendum…’

The only change I think I have made since May 2015 is to shove in some notes from a great essay later that year by the man who wrote the textbook on quantum computers, Michael Nielsen, which would be useful to read as an introduction or instead, HERE.

As always on this blog there is not a single original thought and any value comes from the time I have spent condensing the work of others to save you the time. Please leave corrections in comments.

The PDF of the paper is HERE (amended since first publication to correct an error, see Comments).

 

‘Gödel’s achievement in modern logic is singular and monumental – indeed it is more than a monument, it is a land mark which will remain visible far in space and time.’  John von Neumann.

‘Einstein had often told me that in the late years of his life he has continually sought Gödel’s company in order to have discussions with him. Once he said to me that his own work no longer meant much, that he came to the Institute merely in order to have the privilege of walking home with Gödel.’ Oskar Morgenstern (co-author with von Neumann of the first major work on Game Theory).

‘The world is rational’, Kurt Gödel.

8 thoughts on “Complexity and Prediction Part V: The crisis of mathematical paradoxes, Gödel, Turing and the basis of computing

  1. Its ok quoting Gobel, Turin and Einstein.
    Also ok if you are a university boffin writing yet another 3,000 word thesis of mind boggling crap and jargon that only another boffin understands.
    Where does all this equate with a Politician who patronises 18-25 year olds saying they all like things in chronological order? Where are we going? Prediction or imagination?
    I’m just joe blogs at the other end of all this money and time wasting everything to me is just COMMON SENSE, in which there is no degree – like the ordinary people at the Grenfel Tower disaster – I am merely a 58 year old pawn. Mother of 4 grown children, at the mercy of highly paid, time wasting idiots!

    Like

  2. Predicting human behaviour without reference to axiomatic presuppositions about that same human behaviour? Surely, this was what Gödel’s pulverisation of Hilbert’s attempt at a totalitarian foundationalism for mathematics ruled out wasn’t it? Surely, educational, political, psychological, economic and sociological enquiries are unsuitable objects of THE scientific method because they lack the required ontological stability – being (as the Greeks would have said) merely matters of OPINION (doxa). Opinion is cataclysmically unstable and hence no basis for the predication required of KNOWLEDGE (science/episteme). Respect to you, but I’m amazed you have spent so much time on such a pointless quest.

    Like

  3. The Outher Limits of Reason by Yanovsky is a fabulous book in this domain. All those of a ‘big data is the solution’ bent would do well to read it especially macro economic tinkerers. Even fairly simple puzzles with a few parameters can be unsolvable regardless of resources devoted to the solution. Very accessible book (must have been if I read it!)

    Like

  4. Great and interesting. It is fun to see your mind at work, and this intellectual history is without a doubt one of the hidden mysteries. Thanks for exploring.

    I’d recommend Charles Peltzer’s tremendous “The Annotated Turing,” which takes the 1936 paper sentence by sentence and explains it all. It gives a primer on the diagonal proof, Cantor’s work, &c. The book is in itself a major intellectual achievement. It is much more understandable even than the Franzen book on Godel that you often (nicely) cite.

    Like

  5. One correction so far: “An algebraic number is a number that can be produced by a finite series of algebraic operations.” is false. E.g. the roots of a quintic may not satisfy this, but they do fit the standard definition (any root of a polynomial with integer coefficients).

    Like

  6. Still working through your paper… Interesting thus far..

    On a completely note the fury of the remainers seems to focus on the leave bus and the £350 million per week.

    I agree that this figure is wrong, though my back of a fag packet calculations come to a much larger one.

    For a start nobody on either side appears to have mentioned the other two sources of funding that the EU considers to be it’s own resources.

    Our direct contribution of £18 billion, of which about £10 billion is net, this appears to be the source of ukips £50m a day and the leaves £350m a week.

    The second part of it though is the customs Union tariffs from our trade in imports with the rest of the world. Seems we get somewhat over £3 billion a year from these, though this is only to cover our costs in collecting them. As the EU takes 80% of these tariffs then that would represent about £12 billion of extra revenue to the exchequer, assuming that wto rules aren’t dramatically different to customs Union ones.

    Of course taking us out of the customs Union would also see tariffs under wto rules on imports from the EU. John Redwood’s blog gives an estimate of over £12 billion in revenue to the exchequer here.

    Then you have the small proportion of vat which goes to the EU. Probably a billion or two here. Then the strange fact that we are the seventh largest fish importer in the world, which would surely reverse post brexit and assuming our fishing waters are taken back. How much could we make from selling licences? Couple of billion I would think.

    So ten billion from our contribution, twelve from both imports from the EU and the rest of the world, and a few extra from vat and fishing.

    I’m no economist but it’s difficult to fiddle this to below £36 billion which seems to tie up with Germany’s estimates.

    Clearly this represents closer to £700 million a week net then the controversial £350 million gross figure.

    Feel free to call me an idiot if one has erred.

    Like

  7. A useful summary, but a couple of comments on specific passages:

    “Frege was also trying to reduce all mathematics to logic and show that it is analytic as Hume had argued contra Kant. Frege’s work was therefore the catalyst for what became known as ‘analytical philosophy’.”

    Frege gives two formulations of what he was trying to do – once in the Grundlagen of 1884, and later again in the Grundgesetze, where he characterises what has was trying to do in the Grundlagen“: I sought to make it probable that that arithmetic is a branch of logic, and that no ground of proof needs to be drawn from experience or intuition”. This second expression is actually more exact (see Dummett Frege: Philosophy of Mathematics p 3), but there are two more substantive objections to your remark. Firstly, Frege was indeed using the language of Kant, and adopted his terminology in the Grundlagen, but he never used these expressions again until 1924. “Intuition” translates Anschauung, which is a hard word to translate, but is often used in connection with geometry (as in “spatial intuition” – not in the sense of having a hunch) which is why, after the Russell paradoxes, Frege was playing with the idea at the end of his life of basing arithmetic on geometry, which he did think required intuition (in the relevant sense). Secondly, Analytical philosophy did not derive its name from the Kantian meaning of “analytic”, but from a belief that the correct way to do philosophy was by linguistic analysis – that a philosophical account of thought can be obtained through a philosophical account of language, and that it can only be so obtained. It is this that would make Frege one of the founders of analytical philosophy, not his claim that the truths of arithmetic were analytic.

    “After the war, the ‘Vienna Circle’ developed what they called Logical Positivism out of what they, self-consciously but controversially, thought were the lessons of Wittgenstein’s Tractatus, an extreme empiricism which regarded ‘the true’ as synonymous with ‘what can be proved’ – a dangerous idea and one that Gödel formally disproved with his 1931 paper (see below).”

    It is true that the Vienna Circle was influenced by the Tractatus, but not quite in the way you suggest. The so called principle of verification, that the meaning of a sentence can be given by saying how it could be verified – where verified is something that we do, not merely indicting the statement of affairs, which, if it obtained, would render the sentence true – was proposed as a criterion of meaningfulness, not of truth (although in the Tractatus having sense just meant being either true or false); it was meant to consign metaphysics (because not to subject to verification) to the realm of meaninglessness. Popper subsequently argued that falsifiability was a criterion of science, not of meaning, and therefore believed his criterion avoided the problem that the principle of verification appeared not subject to its own condition. The key error in your quote is the idea that the Tractatus embodied a non-realist conception of truth; there is no consideration given at all in the Tractatus about our practical ability to determine the truth or falsity of sentences; they are true or false according as the world is as they say it is – our ability to ascribe sense to sentences extends beyond our ability to determine their truth. Often truth conditions are compared with assertability conditions. In the case of arithmetic, the realist position often aligns with Platonism – the view that mathematical objects stand in an objective relation to each other independently of what we think – and the opposing view, the constructivist position, is that a mathematical statement is asserted as the consequence of a proof, and in some sense it is the proof that makes it true, rather than revealing to us the pre-existing truth of the theorem. This clearly makes the notion of proof (and of a canonical proof crucial – i.e., understanding what makes a proof a proof).

    Frege was clearly a Platonist – any wff is true or false, whether we are possessed of a proof of it or not. Classical two valued logic operates explicitly within this framework – and employs a wide concept of provability (you mention Hilbert’s finitist standpoint in this regard). Theorems are provable within classical logic that are not provable within intuitionist logic; you mention the difference between intuitionism and formalism as a response to the paradoxes (as was Russell’s Theory of Types), but it would be helpful to say something more about what the difference actually amounts to. The differences are in part philosophical, but also differ in the underlying logics (which are distinct and non-equivalent). For example a constructive proof of an existential statement that a number exists that possesses a certain property requires the proof to say which number possesses that property, rather than simply to show that the statement that all numbers do not possess that property leads to a contradiction; in intuitionistic propositional calculus there is no finite characteristic matrix for the logical constants for example. Although Brouwer’s writing is laced with a chronic psychologism the intuitionists’ objection to classical logic should better be seen to derive from a different philosophy of language.

    Wittgenstein’s writings on the philosophy of mathematics are in fact unpublished notes and notes taken from some lectures (Turing attended some of them by the way) and are generally considered to be mistaken in certain respects (specifically on Gödel). He held the view, not often held today, that philosophy and mathematics had nothing to say to each other, and that philosophy ought not to “interfere with mathematicians”. He did try however to understand where some of our basic thoughts (“intuitions” in another sense) came from about some basic logical-mathematical concepts: logical necessity, following a rule, consistency, provability, convention, Whether his thoughts are persuasive or not is perhaps less important than the considerations they raise.

    If you are interested in looking further I suggest articles included in Dummett’s Truth and Other Enigmas, 1978 (Truth, Realism, The Philosophical Basis of Intuitionistic Logic, The Justification of Deduction).

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s