A post simply to capture a wonderful 2016 lecture by Doug Hofstadter on Gödel and the limits to logic.
Wonderful – in a wonderfully nerdy sense, like so much Hofstadter. (In fact I only stumbled upon it randomly in the side-bar of a discussion of Dave Edmonds on Schlick and the Vienna Circle.)
[Still an important issue for my own theses whether or not Gödel consequences really can be extended to non-number / non-integer contexts in (say) epistemology- real world human epistemology that is. But that of course is the point – any arbitrarily complex formulae or system of formulae – expressible in any formal notation – can be represented in Gödel numbering and their decidability analysed … formally.]
Wonderful – because right from the start Hof is highlighting syntactic properties of sentences or even of integer numbers, strings of digits, symbols or anything (like length or size, a visual aesthetic) when talking about what we can know semantically about them, their content. Syntactic well-formedness and the semantic decidability or truth value of content, etc … every time I see this relationship it still seems nuts. It runs through so much of his work from “Gödel Escher Bach” via strange-loopiness to “Fluid Concepts and Creative Analogies” the former being seminal, the latter being an absolute tour de nerdy force.
Wonderful – because he talks and transforms formal logical notation in real time in his head whilst lecturing.
Wonderful – for the Collatz conjecture which was a new one for me – but is key to seeing the unpredictable size / shape relationship to a theorem, the special semantic content of that kind of string. The rest is basically the clearest possible exposition of what Gödel is about. Did I mention – wonderful?
Encoding a long complex string in a large (but not necessarily long) integer? And what operations can you perform on it, what properties can you extract from it?
Even a string that might represent a Bach composition … ha! … or more to the point, the whole three volume text of Principia Mathematica. This is Gödel numbering – Any string (even a complex mathematical or logical formula or sequence of formulae – the whole of the Principia) can be encoded in a large integer and analysed formally
So, for the integer (Gödel number) form of any arbitrary symbolic string, the analysis of its well-formedness will always be monotonic, convergent on a result, but the decidability of the truth value, the provability of (some part of) the content, may not be and may not be predicted.
Gödel’s formula G, whose number is g,
States that g is not the number of a theorem.
The number g exists (and has complicated number-theoretical properties)
(And yet) G says that it is not a theorem.
Says that it is provable, yet that very statement is not provable.
Not provable because it is true!
All (complete) axiomatic systems have such a (paradoxical) statement.
Goodbye professor Russell.
[Spot the great throw-away remark about the photo of Gödel with “an unidentified peasant”. Brilliant teacher.]
[Lots more 21st C Hofstadter talks on YouTube, covering most aspects of his work … the self-referential loops and analogies.]