Turing versus Rosenberg

Perhaps this would be better on my book review site, but it’s really a question of science, prompted by reading the challenging The Atheist’s Guide to Reality: Enjoying Life without Illusions.

My issue with the book is not atheism but the essential claim of the author – Alex Rosenberg – that human beings cannot reason about anything, can exercise no choice and have no free will and live a completely determined life.

Rosenberg grounds this in the claim that humans cannot have thoughts “about” anything – how can, he asks, your neurons be “about Paris” (or anything else) when they are merely electrical connections? And, he adds, our sense of free will, of conscious decision, is an illusion as demonstrated by multiple experiments that show we have “taken” any decision before we consciously “decide” to take it.

English: Plaque marking Alan Turing's former h...
English: Plaque marking Alan Turing’s former home in Wilmslow, Cheshire. Español: Placa conmemorativa en la antigua casa de Turing (Photo credit: Wikipedia)

In the end I just think this is a tautology. How can the words on a page be “about Paris” either when they are just black ink? We end up abolishing the category of “about” if we follow this argument. Nothing is about anything else.

And how do humans advance their knowledge and understanding if they cannot reason, cannot decide? Knowledge cannot be immanent in experience, surely? Newton did not formulate gravity because being hit on the head by the mythical apple was a form of “percussive engineering” on his neural circuits – he reasoned about the question and yes, that reasoning helped reshape the neural connections, but it was not pre-destined.

And anyone who has read Godel, Escher, Bach will surely see conscious and unconscious decision making closely linked in any case – this is what a “strange loop” is all about.

Ultimately I find myself thinking of Turing’s idea of the “imitation game” and the more general idea that intelligence is what looks like intelligence. Computers have no free will, but they are not necessarily fully deterministic either – we can build a random number generator which is powered by nuclear decay events which, we must believe, are fully stochastic. Such a system could be made to appear as exercising choice in a completely non-deterministic way and look fully human within the bounds of Turing’s game. And when I say it is being “made to appear” to be exercising choice, I think it will be exercising choice in just the same way as we do – because there is no way that we could tell it apart from a human.

Or to take another example – if we build a genetic algorithm to find a heuristic solution to the travelling salesman problem in what sense has the computer not thought “about” the problem in developing its solution?


Incompleteness in the natural world

Gödel Incompleteness Theorem
Gödel Incompleteness Theorem (Photo credit: janoma.cl)

A post inspired by Godel, Escher, Bach, Complexity: A Guided Tour, an article in this week’s New Scientist about the clash between general relativity and quantum mechanics and personal humiliation.

The everyday incompleteness: This is the personal humiliation bit. For the first time ever I went on a “Parkrun” today – the 5km Finsbury Park run, but I dropped out after 2.5km 2km – at the top of a hill and about 250 metres from my front door – I simply thought this is meant to be a leisure activity and I am not enjoying it one little bit. I can offer some excuses – it was really the first time ever I had run outdoors and so it was a bit silly to try a semi-competitive environment for that, I had not warmed up properly and so the first 500 metres were about simply getting breathing and limbs in co-ordination – mais qui s’excuse, s’accuse.

But the sense of incompleteness I want to write about here is not that everyday incompleteness, but a more fundamental one – our inability to fully describe the universe, or rather, a necessary fuzziness in our description.

Let’s begin with three great mathematical or scientific discoveries:

The diagonalisation method and the “incompleteness” of the real numbers: In 1891 Georg Cantor published one of the most beautiful, important and accessible arguments in number theory – through his diagonalisation argument, that proved that the infinity of the real numbers was qualitatively different from and greater than the infinity of the counting numbers.

The infinity of the counting numbers is just what it sounds like – start at one and keep going and you go on infinitely. This is the smallest infinity – called aleph null (\aleph_0 ).

Real numbers include the irrationals – those which cannot be expressed as fractions of counting numbers (Pythagoras shocked himself by discovering that \sqrt 2 was such a number). So the reals are all the numbers along a counting line – every single infinitesimal point along that line.

Few would disagree that there are, say, an infinite number of points between 0 and 1 on such a line. But Cantor showed that the number was uncountably infinite – i.e., we cannot just start counting from the first point and keep going. Here’s a brief proof…

Imagine we start to list all the points between 0 and 1 (in binary) – and we number each point, so…

1 is 0.00000000…..
2 is 0.100000000…..
3 is 0.010000000……
4 is 0.0010000000….
n is 0.{n – 2 0s}1{000……}

You can see this can go on for an infinitely countable number of times….

and so on. Now we decide to ‘flip’ the o or 1 at the index number, so we get:

1 is 0.1000000….
2 is 0.1100000….
3 is 0.0110000….
4 is 0.00110000….

And so on. But although we have already used up all the counting numbers we are now generating new numbers which we have not been able to count – this means we have more than \aleph_0 numbers in the reals, surely? But you argue, let’s just interleave these new numbers into our list like so….

1 is 0.0000000….
2 is 0.1000000…..
3 is 0.0100000….
4 is 0.1100000….
5 is 0.0010000….
6 is 0.0110000….

And so on. This is just another countably infinite set you argue. But, Cantor responds, do the ‘diagonalisation’ trick again and you get…

1 is 0.100000…..
2 is 0.110000….
3 is 0.0110000….
4 is 0.1101000…
5 is 0.00101000…
6 is 0.0110010….

And again we have new numbers, busting the countability of the set. And the point is this: no matter how many times you add the new numbers produced by diagonalisation into your counting list, diagonalisation will produce numbers you have not yet accounted for. From set theory you can show that while the counting numbers are of order (analogous to size) \aleph_0 , the reals are of order 2^{\aleph_0} , a far far bigger number – literally an uncountably bigger number.

Gödel’s Incompleteness Theorems: These are not amenable to a blog post length demonstration, but amount to this – we can state mathematical statements we know to be true but we cannot design a complete proof system that incorporates them – or we can state mathematical truths but we cannot build a self-contained system that proves they are true. The analogy with diagonalisation is that we know how to write out any real number between 0 and 1, but we cannot design a system (such as a computer program) that will write them all out – we have to keep ‘breaking’ the system by diagonalising it to find the missing numbers our rules will not generate for us. Gödel’s demonstration of this in 1931 was profoundly shocking to mathematicians as it appeared to many of them to completely undermine the very purpose of maths.

Turing’s Halting Problem: Very closely related to both Gödel’s incompleteness theorems and Cantor’s diagonalisation proof is Alan Turing’s formulation of the ‘halting problem’. Turing proposed a basic model of a computer – what we now refer to as a Turing machine – as an infinite paper tape and a reader (of the tape) and writer (to the tape). The tape’s contents can be interpreted as instructions to move, to write to the tape or to change the machine’s internal state (and that state can determine how the instructions are interpreted).

Now such a machine can easily be made of go into an infinite loop e.g.,:

  • The machine begins in the ‘start’ state and reads the tape.  If it reads a 0 or 1 it moves to the right and changes its state to ‘even’.
  • If the machine is in the state ‘even’ it reads the tape. If it reads a 0 or 1 it moves to the left and changes its state to ‘start’

You can see that if the tape is marked with two 0s or two 1s or any combination of 0 or 1 in the first two places the machine will loop for ever.

The halting problem is this – can we design a Turing machine that will tell us if a given machine and its instructions will fall into an infinite loop? Turing proved  we cannot without having to discuss any particular methodology … here’s my attempt to recreate his proof:

We can model any other Turing machine though a set of instructions on the tape, so if we have machine T we can have have it model machine M with instructions I : i.e., T(M, I)

Let us say T can tell whether M will halt or loop forever with instructions I – we don’t need to understand how it does it, just suppose that it does. So if (M, I) will halt T writes ‘yes’, otherwise it writes ‘no’.

Now let us design another machine T^\prime that takes T(M,I) its input but here T^\prime loops forever if T writes ‘yes’ and halts if T writes ‘no’.

Then we have:

M(I) halts or loops – T(M, I) halts – T^\prime loops forever.

But what if we feed T^\prime the input of T^\prime(T(M, I)?

M(I) halts or loops – T(M, I) halts – T^\prime(T(M,I)) loops forever – T^\prime(T^\prime(T(M,I))) – ??

Because if the second T^\prime(T^\prime(T(M,I))) halted then that would imply that the first had halted – but it is meant to loop forever, and so on…

As with Gödel we have reached a contradiction and so we cannot go further and must conclude that we cannot build a Turing machine (computer) that can solve the halting problem.

Quantum mechanics: The classic, Copenhagen, formulation of quantum mechanics states that the uncertainty of the theory collapses when we observe the world, but the “quantum worlds” theory suggests that actually the various outcomes do take place and we are just experiencing one of them at any given time. The experimental backup for the many worlds theory comes from quantum ‘double-slit’ experiments which suggest particles leave traces of their multiple states in every ‘world’.

What intrigues me: What if our limiting theories – the halting problem, Gödel’s incompleteness theorem, the uncountable infinite, were actually the equivalents of the Copenhagen formulation and, in fact, maths was also a “many world” domain where the incompleteness of the theories was actually the deeper reality – in other words the Turing machine can both loop forever and halt? This is probably, almost certainly, a very naïve analogy between the different theories but, lying in the bath and contemplating my humiliation via incompleteness this morning, it struck me as worth exploring at least.

A (partial) answer to my Goedelian conundrum?

Douglas Hofstadter in Bologna, Italy
Douglas Hofstadter in Bologna, Italy (Photo credit: Wikipedia)

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.:

TRUE\{a\} can tell us whether the number theoretical statement with Goedel number a is true.

So now we posit, T with Goedel number t :

\exists a:<\sim TRUE\{a\} \wedge ARITHMOQUINE\{a^{\prime\prime},a\}>

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 a^{\prime\prime}, with the Goedel number for the statement itself…

\exists a:<\sim TRUE\{a\} \wedge ARITHMOQUINE\{SSS \ldots SSS0,a\}>

Which we can state as “the arithmoquinification of t is the Goedel number of a false statement”.

But the arithmoquinification of t is T ‘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 TRUE\{a\} 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!

Some notes on Hofstadter’s Typographical Number Theory

In Godel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter outlines his axiomatic “Typographical Number Theory” and sets certain problems for the reader – one is to show that b (a variable) is a power of 2.

These are my notes in trying to demonstrate this (hopefully understandable to anyone who knows a bit of symbolic logic and has a passing knowledge of Peano’s axioms.

My reasoning runs like this: if a number is a power of two then it has no prime factors other than 2 (and 1, if we count that as a prime) – see the earlier entry on the fundamental theorem of arithmetic.

A prime (a) in TNT:

\exists a: \sim \exists a^{\prime}: \sim \exists a^{\prime\prime}: < a^{\prime}.a^{\prime\prime}=a \wedge \sim a^{\prime} = 0 \wedge \sim a^{\prime} = S0 \wedge \sim a^{\prime\prime} = 0 \wedge \sim a^{\prime\prime} = S0>

First Update: Now realise there is a simpler way of stating a prime in TNT – namely that there is no two numbers bigger than one the product of which is the number we seek:

\exists a: \sim \exists a^{\prime}: \exists a^{\prime\prime}: SSa^{\prime}.SSa^{\prime\prime} = a

Second update:

So, we have a definition for a prime, a, and we can set  a to a prime other than 2.

\exists d: \exists a: \sim \exists a^{\prime}: \exists a^{\prime\prime}: <SSa^{\prime}.SSa^{\prime\prime} = a \wedge \sim a = SS0>


\exists b: \exists c: \sim \exists a: \sim \exists a^{\prime}: \exists a^{\prime\prime}: <SSa^{\prime}.SSa^{\prime\prime} = a \wedge \sim a = SS0 \wedge \sim b = a.c>

I think this is a sufficient definition for “b is a power of 2”, as we know that all numbers are products of primes and we have ruled out any prime other 2 being a factor of b. Is that right?

On further thought I don’t think that’s enough, because we need to specify that b is a multiple of 2.

So what about this?

\exists b: \exists c: \exists d: \sim \exists a: \sim \exists a^{\prime}: \exists a^{\prime\prime}: <SSa^{\prime}.SSa^{\prime\prime} = a \wedge \sim a = SS0 \wedge \sim b = a.c \wedge b = SS0.d>

So has that nailed it?

How I discovered the fundamental theorem of arithmetic by chance

Cover of "Gödel, Escher, Bach: An Eternal...
Cover via Amazon

Actually, of course, I rediscovered it.

I have been attempting to read, for the third time Douglas Hofstadter‘s celebrated Godel, Escher, Bach: I bought a copy in Washington DC in 2009 and loved it (though didn’t get very far before I put it down for some reason) but I have always struggled to get deeply into it: it’s plainly a great book – though having read more on Turing these days I am not sure I’d subscribe to what appears to be the core thesis – but it’s not an easy read.

(Though Hofstadter’s preface did inspire me three years ago to read the brilliantly compact Godel’s Proof– buy, steal or borrow a copy if you are at all interested in maths.)

This time round I am feeling more confident I’ll make progress, it just seems a bit easier to grasp – possibly because I am feeling more confident about maths these days (not that there is any higher maths in it – but grasping some of the more complex stuff does seem to help with all of it.)

So I got the part known as the “MU puzzle” – can you go from the axiom MI to the theorem MU following the rules of the formal system he sets out. I thought – oh, yes, easy, just find a power of two that is also a multiple of three – and in my head I start going 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 – a list I have been familiar with for thirty three years or so. But none of them are multiples of three.

Now, presumably anyone who knows anything about prime numbers has by now said “of course they are not, haven’t you heard of the fundamental theorem of arithmetic?” – well it seems the answer to that is “err, no”.

Or, if I had, I never really grasped its meaning. Each number cn be factorised into a unique set of primes (if a prime then just itself, of course). That precludes any power of two having as a factor any other prime number (of which three is of course one). It’s really epically important in terms of understanding numbers and I am slightly shocked and puzzled I have never really understood it before now.

Bought on a whim but seems like a good one

This diagram shows the syntactic entities whic...
Image via Wikipedia

I bought this book this evening on the way home from work – The Annotated Turing – and have already got through fifty pages.

(Actually I wish I had bought it from Amazon because the price there is less than half I paid for it).

Those pages covered much of the same ground as the early chapters of  Godel, Escher, Bach: An Eternal Golden Braid – a much more famous book (and not a bad read) –  and in a more formal, mathematical way, but it also seems to do it in a much clearer fashion.

So, while I haven’t yet got to the chapters that dissect Turing’s On Computable Numbers, with an Application to the Entscheidungsproblem, so far I have no hesitation in recommending it as a good introduction to the issues of computability.