[FOM] Mirna Dzamonja on an alleged "crisis" in foundations

Lawrence Paulson lp15 at cam.ac.uk
Thu Mar 7 06:46:07 EST 2019

On 5 Mar 2019, at 19:25, José Manuel Rodríguez Caballero <josephcmac at gmail.com> wrote:
> The crisis in contemporary mathematics is not in its foundations, but in accumulation of mistakes, because there are many papers and books, written by important mathematicians, with mistakes and gaps. Some of these mistakes are because of the use of the word "obvious". As Barkley Rosser said: if Church says it is obvious, they've all noticed it for an hour; if Weyl says it's obvious, von Neumann can prove it; if Lefschetz says it's obvious, then it's fake.

Recently I've been teaching computation theory and have been struck by the contrast in the level of rigour between what we teach now and what Alan Turing wrote in 1937:


Today's students are presented with functions for encoding pairs and sequences of natural numbers in the form of a natural number, and the corresponding decoding functions. They are presented with the full and precise code for a universal machine (for register machines rather than Turing machines). Now let us see how Alan Turing enumerated his machines:

'Let us write down all expressions so formed from the table for the machine and separate them by semi-colons. In this way we obtain a complete description of the machine. In this description we shall replace q(i) by the letter "D" followed by the letter "A" repeated i times, and S(j) by "D" followed by "C" repeated j times. This new description of the machine may be called the standard description (S.D). It is made up entirely from the letters "A", "C" , "D", "L", "R", "N", and from ";".

If finally we replace "A" by "1", "C" by "2", "D" by "3", "L" by "4", "R" by "5" , "N" by "6" , and ";" by "7" we shall have a description of the machine in the form of an arabic numeral.'

Turing was surely aware of particular bijections between pairs of natural numbers and natural numbers. We have to wonder why he adopted such naïve methods, which surely complicated the design of the universal machine. It's also interesting that this paper derives a number of fundamental results without clearly stating what is being proved. For example, the unsolvability of the halting problem is treated in section 8, but without an actual theorem statement.

Was this level of rigour typical of those times?

Larry Paulson

More information about the FOM mailing list