Last week I puzzled over what seemed to me to be the hand waiving dismissal, by both Alan Turing and Douglas Hofstadter of what I saw as the problem of humans being able to write true statements that the formal systems employed by computers could not determine – the problem thrown up by Goedel’s Incompleteness Theorems.
Well, Douglas Hofstadter has now come to his own (partial) rescue as I continue to read on through Godel, Escher, Bach – as he describes Tarski’s Theorem, which essentially states that humans cannot determine all such statements either (unless we posit the Church-Turing thesis is wrong, of course and there is some inner human computational magic we have yet to describe).
I am now going to quickly run through Hofstadter’s exposition – it might not mean too much to those of you not familiar with GEB, but if so and if you are interested in computation (and genetics and music) and you want to improve your mind this summer you could always think about buying the book. I don’t promise it’s an easy read, the style can vary from the nerdy to the deeply frustrating, but it is still a rewarding read.
So here goes:
We imagine we have a procedure that can determine the truth of a number theoretical statement, i.e.:
can tell us whether the number theoretical statement with Goedel number a is true.
So now we posit, with Goedel number :
Now, of you have read GEB you will know that to “arithmoquine” a number theoretical statement is to replace the free variable – in this case , with the Goedel number for the statement itself…
Which we can state as “the arithmoquinification of is the Goedel number of a false statement”.
But the arithmoquinification of is ‘s own number, so this statement is the equivalent of saying “this statement is false”: just another version of the famous Epimenides Paradox, but one that is decidedly not hand waving in form: it’s about natural numbers.
The outcome is that cannot exist without our whole idea of natural numbers collapsing and we are forced to conclude there is no formal way of deciding what is a true statement of theoretical number theory using only theoretical number theory – and so humans are no better off than computers in this regard: we use concepts from without the formal theory to establish truth and we could surely program our computers to do the same. Turing’s “imitation game” conception of intelligent machines thus survives.
At least I think so!
- Turing, Hofstadter, Bach – with some Cherla thrown in (cartesianproduct.wordpress.com)
- Book Review – I Am A Strange Loop (vainolo.com)
- Online reading seminar for Zhang’s “bounded gaps between primes” (terrytao.wordpress.com)
- Scientists capture first direct proof of Hofstadter butterfly effect (scienceblog.com)
- I just can’t resist: there are infinitely many pairs of primes at most 59470640 apart (sbseminar.wordpress.com)
- Infinite Medium / Unlimited Meaning (manoftheword.com)
- [tt] NS 2915: Douglas Hofstadter and Emmanuel Sander: Analogy: The vital talent that fuels our minds (stirling-westrup-tt.blogspot.com)
- Introduction to MetaGödel (metagodel.wordpress.com)
- Keira Knightley to join Benedict Cumberbatch in Alan Turing biopic? (digitalspy.co.uk)
- Keira Knightley may join to Benedict Cumberbatch in Turing biopic (telegraph.co.uk)
Great news – the man’s memory deserves nothing more than the actor who has proved himself to be both great and edgy in recent work (he’s certainly not the milque toast figure the start of his career briefly suggested.)
As a geek, of course, I hope that the film will try to explain, just a little his achievements.
But how can you explain the ideas of computability and the Church-Turing thesis in a popular film? A tough one, but I suppose you could do something.
The Bletchley Park “bombe” and the idea that the weakness of the German Enigma machine – that it would never map a letter to itself (eg., in any message “e” would never be encrypted as “e”) – could be used to break the code (if a combination of a guessed plain text, usually a weather report, at the start of the message , and the initial key settings produced code that mapped letters to themselves then the initial settings were wrong) – is probably easier to explain.
And don’t forget about SIGSALY, the voice encryption system Turing worked on with Bell Labs. As a piece of engineering this is probably impossible to over-estimate in importance: as the first practical pulse code modulation system it could even be said to be the mother the mobile phone, or at least its grand aunt.
And, of course, let me again plug my book of the year: The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine
- Leonardo DiCaprio To Play Alan Turing? (news.slashdot.org)
- Leonardo di Caprio to play Alan Turing? (i-programmer.info)
- Leonardo DiCaprio To Play Gay Enigma Code Breaker Alan Turing? (pinkbananaworld.com)
- DiCaprio Rumored To Play WWII Codebreaker Alan Turing – And Every Gay Figure In History Ever (queerty.com)
- Alan Turing’s Biopic Might Get the Hollywood Hunk Treatment from Leo DiCaprio [Movies] (gizmodo.com)
- Leonardo DiCaprio tipped to play codebreaker Alan Turing (guardian.co.uk)