The importance of Turing’s findings

Yesterday I was speaking to a friend – who knows about computers but not about computer science – who told me this blog was just too difficult: so I thought I’d seek to order my own thoughts after reading The Annotated Turing and assist humanity in general (!) by writing a piece that explains what I think is the most fundamental finding from Turing’s famous On Computable Numbers paper.

To begin one must remember that Turing’s paper is not about electronic computers at all: indeed while in the paper he refers to “computers” – what he means is a person who computes.

Turing’s paper does describe an entirely theoretical mechanical machine that replicates the actions of a “computer” in solving a mathematical process through simple steps. You could think of those steps in this form if you were the computer adding 1 to 1:

• Read in the first number: 1
• Read in the operation: +
• Read in the second number: 1
• Apply the operation to both numbers
• Write out the answer

Turing’s argument is that the only numbers we can compute are those that can be computed in this mechanical way. This, in itself, was – and in a way remains – a controversial statement because it says that at the heart of human consciousness is a mechanical process and that, fundamentally, there is nothing special about consciousness.

In a way this flies in the face of all our experience of (digital) computers. Whatever else we know about them we know they cannot “think” – they are certainly mechanical (in the sense that they solve problems in the step-by-step way outlined above ) but they are so radically less powerful, it would seem, that our consciousness, our thinking must be built upon something else.

This – the idea that consciousness is more than mechanical – is rather out of favour these days but it still has its adherents: you can read more about the fascinating “hard problem of consciousness” if you want to read more about it, for here we are going to take the materialist approach and argue that the brain is indeed a mechanical processor, albeit one that (perhaps because of massive parallelism, or specific adaptation, or whatever) is hugely ahead of where our electronic computers are today in certain fields (though the gap is clearly closing on just about all fronts).

So if we accept that the only means available of calculating is a mechanical process then we must also accept Turing’s finding that we can only calculate a tiny minority of numbers or problems.

To explain this we need to look at the concept of infinity, or more properly infinities, because, at least according to the widely accepted theory of Georg Cantor, there is more than one infinity – indeed there are an infinite number of infinities all of a different size – or order as the size is referred too.

Sounds like nonsense, doesn’t it? But here’s a mind experiment to help you understand.

Think of a ruler, marked out in centimetres (or inches if you are old fashioned). But this ruler stretches on infinitely – so an infinite number of centimetre markings are present. But each one of these markings can be associated with a natural number, zero, one, two and so on. This is an infinite list which is said to be enumerable (countable) – a number can be assigned each member of the set of markings on the ruler. The number of members a set has is called its cardinality, and so this set has what is called the cardinality of aleph null:

But think of that ruler again – how many points are there between the different markings? Clearly we can divide the ruler up over and over again and that means we must have a bigger infinity than aleph zero.

This infinity is of this order  – two raised to the power of aleph null – we discuss why below:

An aside: the continuum hypothesis

According to the continuum hypothesis  aleph one is the so-called cardinality of the continuum. (Aleph one being the next biggest set of infinite numbers than aleph null: the continuum hypothesis):

And so, goes the theory, aleph one is of the same order as the number of real numbers. A real number being an integer number followed by a decimal point and an infinite (aleph null order) set of numbers – in the case of the natural numbers this is an infinite set of zeros, etc. Hence, the hypothesis states:

======

In any case the important number here is two to the power of aleph null – the order of the set of real numbers.

And why is this the order of the real numbers – because it is the order of the power set of the natural numbers. The power set is the number of subsets of a given set:

To explain why this is the order of the set of real numbers think of a binary (0 or 1) expansion after the decimal point – each digit will then be countable – ie there will be a first digit, a tenth digit and a ten millionth digit – that means it is of order aleph null, but the way in which the 0 and 1s can be ordered is the power set of the countable numbers, in other words two to the power of aleph null: a number that by definition is too big to count:

Now, what Turing’s paper shows is that we can only build a machine that computes (in other words calculate) a countable number of numbers – in other words we can only calculate aleph null numbers – or alternatively, solve aleph null problems.

But the number of real numbers is two to the power of aleph null, a much bigger number (to repeat, it is actually too big to count).

This is was a shattering result to a generate of mathematicians who were accustomed to the idea that all mathematical problems were solvable.

On 8 August 1900, one of greatest mathematicians of the nineteenth and twentieth century, David Hilbert, told the Second International Congress of Mathematicians in Paris:

“However unapproachable these [mathematical] problems may seem to us and however helpless we stand before them, we have, nevertheless, firm conviction that their solution must follow by a finite number of purely logical processes … This conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call. There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus.”

But on 12 November 1936, the formal publication date of Turing’s paper, that confidence was destroyed for ever. An uncountable number of mathematical problems simply cannot be solved.

Related Articles

• Bought on a whim but seems like a good one (cartesianproduct.wordpress.com)

Advertisement