Back    All discussions

Gödel and Turing: Al Ala Akbar (الآلة أكبر The Machine is the Greatest)


This thread has been abusively deleted. The Philpapers Team offered me the opportunity to restore it.

"How many threads do you need to restore? Combining multiple posts into one would be a way to get around the limitation on 2 posts, and would also be less work for you. Since they were previously accepted, we'll make sure to accept them if you notify us ahead of time with the subject heading." The PhilPapers Team


1 Turing and the Myth of Universality

There is a strong, not to say absolute belief in the consistency of Turing's thesis, which can be, informally, expressed as such: what a computer can do, any other computer can.

Let us start with the simplest expression of all:

1) 0+1=1

It will be obvious to anyone that any computer worth its silicone, or any other material substrate, will be able to compute (1).

What does that say about universal computing?

Well, that's just it, really. It does not say anything at all. All it shows is that, once the problem has been solved, or at least, put in a form that makes solutions possible, there is no reason to think that it could not be put in a form suitable for a machine. Does that make the machine universal?

I dare say that there is no such beast. I do not know of any universal computer. There are many problems that cannot be solved by computers as we know them, and that has nothing to do with memory capacity or processing speed.

Second, transferring a problem from one system to the other, assuming it is computable, means creating new ways of looking at the problem which has nothing to do with the machines involved, and all with human imagination and intelligence.

If we decide to let a connectionist network compute (1), we will have to redefine (1) in such a way that a neural network will be able to process it. That is not something any computer can do, unless we already have written a program for that.

Universal computing seems therefore synonymous to the ability of the human mind to solve the same problem in different ways. Whether that is always possible, or whether some problems only accept of a single solution is a complex issue I have no pretension of solving.

All I can say is that I believe that the only universal computer we know, so far, is the human mind.

Which brings us to the issue of computability. Put very simply, it means that ability of the human mind to process a problem in such a way that it becomes possible to have a machine take care of it. In other words, "computability" would simply mean "intelligibility", but then limited by the necessity of mechanical realization.

The problem with such a definition is that it offers neither help nor hope. We will know of a problem if it is computable once we have done it. But in case of failure? That is the whole problem in a nutshell. Is there a formula which would make it possible for us to decide, in advance, whether something is computable?

This sounds suspiciously like Gödel's pretension that he has an algorithm that proves the incompleteness of any (arithmetic) theory: the machine as guardian of the limits to the human mind.

Allow me to shudder in awed silence.

Oh, by the way, somewhere along the line, we will meet Cantor again. The guy is everywhere.


2 Goldbach's conjecture

How come we cannot prove this conjuncture? No counter-example has been found yet, so that the regularity of the relation is undeniable. Still, the mathematical/logical proof eludes us.

It sounds very much like any empirical regularity: we can have laws that describe them, but no logical proof would ever take the place of reasonable conviction.

What if Goldbach's conjecture was just like an empirical law? But then, we would need to (re)define the relations between numbers as empirical. Is that even possible?

Let us see. Let us take

1) 3+4=7

Does (1) strike you as empirical? Well, it does me. There is nothing really necessary in the fact that 3+4=7. Unless of course you have already learned how to count. Which means that you know that 7 can be equal to 1+6, 2+5, 3+4. It seems like the meaning of 7 compels you to accept the truthfulness of 3+4. But is it the meaning of the numeral, or the number? And how could we distinguish cases where we are talking of one and not of the other?

3+4 represents a quantity which we can easily imagine and manipulate when we encounter it. It has taken Man millenia to come to such clever labels as numerals, and when we now say '7' we immediately know what it stands for. I doubt that is the case for school children who still have to learn by rote their tables. For them 3+4=7, even if they have practiced it with blocks and colors, is just an expression that they must be able to recite mindlessly:

3+4 is 7, and 3 times 3 is nine.

Back to the question whether 3+4, when considered as actual objects and action of adding, is something that could be known a priori.

What do you get if you add 4 stones to 3 stones. Euh, what was 'adding' again? Right. I have so many stones, and you call them 3, then I add those stones, which you called 4. I now have many more stones that I first had. In fact, I am pretty sure that I have now 3+4 stones. Oh, is that what you mean by seven? Just like thirteen is 10+3, right? Or twenty and one?

Okay, is (1) now empirical or logical? Euh, let me sleep on it? No, you wanna know right now? Okay.

Well, when I throw one heap of stones on the other, I can see that I get a bigger heap. That is certainly an empirical fact. In another reality, the bigger heap could have swallowed the smaller one, or the other way around.

But then we get to the names or numerals. They are certainly random, but not in their relation to each other or to the quantities they are said to name. There is certainly a logic behind it all.

How many children older than 10 do you know who have ever had the patience of counting until 10000, or any other high number, in steps of 1? How many would not know how much 10000 + 325 is? In other words, their answer had nothing to do with the fact whether they ever had before counted 10325 things. It was purely logical, following rules they had learned at school.

And herein lies the problem. Mathematical, or at least, arithmetical expressions, seem to have a double nature. Their genesis is entirely empirical, but the rules that have been distilled out of this practice are algorithmic. Just like weaving, or carpenting. A master teaches his apprentices how to weave a basket or build a table. The rules he gives his pupils make sense, they can be considered as logical, even if it has taken Man a very long time to discover them. They are also algorithmic.

Let us stop right here and simply acknowledge the double nature of (1) without drawing any final conclusions we might regret later.

What does it have to do with Goldbach's conjecture?

Well, simply this: if mathematical expressions have at least one empirical dimension, next to another one which you may call logical or whatever you wish, then it becomes quite understandable why we are unable to prove such a conjecture. After all, we want to decide, once and for all, of the nature of the result we would obtain if we added two heaps together. And 3+4 has taught us that such a result is purely empirical, even if we have learned to handle it as a logical fact. Just like any carpenter would tell you that going against the grain of the wood will cause splintering unless you take appropriate precautions.

The moral of the story would be that it should not be considered as strange that we are unable to prove Goldbach's conjecture. That in fact, it would be stranger it we could.


3 Last Fermat Theorem

[Goldbach's Conjecture: "Every even integer greater than 2 can be expressed as the sum of two primes"

LFT: "xn+yn = zn has no solutions in positive integers if n > 2" (Nigel Boston, "The Proof of Fermat’s Last Theorem", 2003)]

Here is my problem. I have claimed that the first conjecture could not be solved because it pointed to an empirical fact. The same can be said of LFT, and this latter has been solved by Wiles in the 90's.

What gives?

x2+y2=z2, the famous Pythagorean Theorem, is definitely an empirical statement. There is no logical relation between x, y and z, so there is no reason there should be one for their squares, or at least, none that neither the Ancient Greeks nor modern mathematicians could think of.The aim now is to prove that there are no solutions for


Which, according to Mathematicians, has been proved correct by Wiles.

Wile's proof is indirect, by way of elliptic curves and more complex and advanced geometry.As such the expression xn+yn=zn has not been solved. My claim is that it also cannot be solved in this form since there is no logical relation between the terms. An indirect proof could, and apparently, did, unveil the rule behind the conjecture.I am afraid I could not give you a summary of the proof since it involves area of Mathematics I didn't even know existed. All I know is that it somehow involves elliptic curves, and the way they are expressed in strange equations like y2= x3 and something.What I do find interesting, is that it concerns the possibility of curves to be drawn by such equations.

Well, it took more than 300 years, and quite a detour before the conjecture could be, indirectly proved. As I understand it, it goes like this: xn+yn=zn, for n >2, can be understood as expressing some kind of mathematical object, an elliptical curve. If we consider x, y and z as parameters in a multidimensional plane, we can draw different curves with different properties, but none that would have the parameters have all the same power. That takes care of the negative aspect of the conjecture and proves Fermat right, even if he himself could never have proven his own conjecture, since the mathematical means used in the proof were only discovered long after his death (see Peter Brown's blog in the Nautilus: "How Math’s Most Famous Proof Nearly Broke", 2015).

I personally find this less interesting than the fact that the conjecture could not have been solved in a direct manner, just like the Pythagorean Theorem could not have been deduced from logical principles. Geometry, in whatever form, is nothing but empirical.

In this context, I find Euler's article "Observations on a theorem of Fermat and others on looking at prime numbers" (1737/2005) quite educative. He analyses different theorems of Number theory and succeeds in proving them wrong, which does not prevent him from declaring, concerning another theorem: "I have drawn these observations from a certain theorem which is not inelegant, a demonstration of which I do not however have, though in fact I am most certain of the truth of this."

First, there is the matter of what he calls observations. He of course means simply the result of his calculations made in the privacy of his study room. But it does indicate an unconventional view of mathematical labor. Calculations are done by applying all kinds of rules which, to a layman, appear to be very abstract. But then, we must not forget that another genius, less than two centuries later, Albert Einstein, would revolutionize physics while working as a civil servant. All his experiments on space, light, etc.. were thought-experiments. Which gives quite another twist to the expression "empirical". Well, to be absolutely honest, Euler's results were less theoretical than Einstein's. There is nothing theoretical in calculations as such. Saying that if you have one sack of grain weighing 50kg and divide the content in two equal parts, you will end up with 2x25kg, I dare claim such a result as empirical and not theoretical, even if it has not happened yet.

This is where an allegedly analytical statement loses its abstract nature and becomes more than a mere prediction, an absolute certainty as long as the world remains as it has always been.

It is, I think, this analytical character, coupled with the empirical certainty, that throws so many thinkers out of balance. And Gödel could be accused of anything but being a balanced figure. (see Rebecca Goldstein "Incompleteness", 2005)


4 The Reality of Mathematical existence

However one chooses to interpret Plato, there seems to be a stable relationship between this world and that of eternal forms. The question of course is whether everything in this world has its counterpart in the Platonist dimension. For instance, do imaginary objects also have an eternal form? Please notice that this does not concern the question whether imaginary objects can be said to exist. Like I said so many times, I will go along with any definition of existence you may feel comfortable with. No questions asked. Even in bitcoin.

To make my point hopefully clearer: let us take the idea of a power set. I already mentioned the fact elsewhere that power sets cannot be real. You cannot turn, for instance, three objects into eight.

That brings a fundamental distinction between some sets and others into light. The set of three objects, or at least, the objects themselves, can be considered as real, even if only in our imagination. But once we start thinking of all the sets we can form with those objects, even our imagination would seem to hesitate.

We can imagine three sets of one; one set of one and one of two objects; or all three objects together. And that's it. Also, each of these cases can only exist by itself, at the exclusion of the others.

You cannot form two different sets with the same objects, that would be having your cake and eating it too.

To be able to form a power set, you would need duplicates of each object. Like this:





What is then the status of this duplicates? Are they real like the other objects are real, or are they "really imaginary", while their originals can be said to be "simply imaginary"?

Note that it is not simply a matter of being the duplicate of an eternal form. When I say 1+1=2, I am using two distinct objects both called '1'. Without this possibility there would be no mathematics.

In this sense, both 1's are real.

That is certainly not simply the case with the 1's in a power set. They are all supposed to represent one and only one object.

It seems to me that even the imaginary world has to be divided in two dimensions, one being "real", the other "imaginary". The real part of the imaginary dimension is the part that could, somehow, accede to the real dimension; while the imaginary part of the our imagination would be forever be cut off from reality.

The conclusion we are led too is certainly not easy to accept for everybody. It would mean that statements about, for instance, power sets, belong to a realm beyond "redemption". That would make of an important part of Mathematics a fiction in the true sense of the word. After all, even fictions, at least most of them, could be realized under the right conditions. But even cloning the elements of a set would not make a power set real.


Gödel and Turing: Al Ala Akbar (الآلة أكبر The Machine is the Greatest)
You mentioned Wile's proof was indirect.  The only way to prove a negative proposition is by indirection.  Assume the positive and show  it leads to a contradiction.  The simplest example I know is to show that the square root of two is not rational.  The way to prove it is to show that the assumption 2 = m^2/n^2  leads to a contradiction.  Which is fairly easy.  Assuming wlog  that m, n are relatively prime  our assumption leads quickly to the conclusion that both m and n are even which contradicts the assumption that m and n are in lowest terms.
I don't know of any negative proposition that has a direct proof.   NB: I am assuming the negative proposition is not trivially the negation of a positive proposition which is easy to prove.

Gödel and Turing: Al Ala Akbar (الآلة أكبر The Machine is the Greatest)
Reply to Robert Kolker
The proof of √2
Thank you for your comment. It compelled me to make explicit thoughts that were only vaguely present to my mind. Here is what I arrived at:
The Pythagorean theorem was an empirical, geometrical discovery, long before algebra had reached maturity: the square of the hypotenuse, when both sides are equal to 1, is irrational. 2 is therefore an irrational number.
The algebraic proof is supposed to show the necessity of such an empirical result. That would mean that the Pythagorean theorem was in fact logically necessary.
How can we we reconcile both views, the historical empirical result, with the logical necessity? Is it simply a matter of hindsight, that it was always a logical truth, but too hidden to be found out by formal means at that time, because mathematics was not advanced enough?
It would seem so, since a student learning of the formal proof, but ignorant of geometry, would be able to arrive to the conclusion that the value of the hypotenuse, when both sides are each equal to unity, has to be irrational!
That would be a great victory for formalists, logicists and realists alike.

Let us review the facts.

The fact that the square of hypotenuse is equal to the sum of the squares of the sides remains an empirical fact. It could have been otherwise. But once the rule was discovered, all the mathematicians needed for their proof of the irrationality of 2, even at the time of the Pythagoras himself, was to give each side the length of unity.

It would have been different if the Pythagorean theorem had been found out to mean that the sum of the squares of the sides was, say, equal to two times the length of the longest side. 2 would then still be an irrational number, even if it would not be tied anymore to the historical, empirical result of the hypotenuse of a right triangle.

Apparently, we can say of the expression a²+b²=c² that the result will be irrational in case both sides are equal to unity, and in fact nothing more than that. The irrationality of 2 seems to be the only general remark we are able to place. And that remark is indeed based on the logic of numbers.

In conclusion, logical necessity, the irrationality of 2, has no influence on the empirical nature of the Pythagorean expression.
A student, well versed in algebra, but ignorant of geometry, would be unable to find the truth of the Pythagorean theorem by himself. Even if, once he has learned the formula, he would immediately be able to deduce the irrationality of the length of the hypotenuse in case both sides are equal to 1.

I seem therefore justified in believing that, just like 
aⁿ+bⁿ=cⁿ is also an empirical law and could not therefore be found by logical reasoning alone.

Gödel and Turing: Al Ala Akbar (الآلة أكبر The Machine is the Greatest)
What are factors? I still think they are nectarines. And that is not some thought out lyrics by recently deceased David Bowie.