This story is about optimists, people who always look at the sunny side of life.
Optimism is a healthy characteristic of optimistic people, but it may sometimes cause
thoughtlessness.
When a word ends with -ism, it often means some kind of exaggeration.
This applies to 'formalism' too. About 1900, the famous German mathematician Hilbert said that it was time to
set up the arithmetical theory of natural numbers with the axiomatic method.
Mathematicians formulated a 'language' for this arithmetical theory, and they called some of its formulas
'axioms' (first propositions); all other truths of arithmetic were to be deduced as propositions
from the axioms.
But in 1931, his fellow countryman Kurt Gödel proved that it is impossible to deduce as
propositions all truths of arithmetic. Indeed, he constructed in an ingenious way a complicated
formula in the language of arithmetic which eventually means nothing else but "this formula is not
a proposition". Assuming that all propositions of arithmetic indicate truths, we conclude that this
formula is not a proposition, but then it does indicate a truth.
So, this stopped the formalistic Hilbert project.
A similar project was 'calculism'. The calculists wished to have for each sequence A of natural
numbers a computer program which, after input of a natural number n, yields as output the n-th
term A(n) of the sequence within a finite space of time (for example within a million years).
This computer program would have to work only on an ideal computer having no fysical limitations
(as to memory space e.a.). One could in principle replace such a computer by a people of
calculators who continue calculating from father to son. We are going to see that this project
is fundamentally impracticable as well.
Call a sequence 'calculable' if and only if one can write for it such a computer program.
The sequence and the computer program belong together. The listing of the computer program is a
text. You can place the listings of all computer programs of the ideal computer in one infinite
list in order of length and (in case of equal length) alphabet (use the ascii codenumbers). Now go with the eyes past all
computer programs in the list, and call the sequence belonging to the first computer program
you meet of a calculable sequence, A1, the sequence belonging to the second program of a
calculable sequence, A2, etcetera ad infinitum.
You may do this in your mind, but can it be done in reality (in a project continued from father
to son) ?
Consider the sequence B with, for each natural number n, B(n):=An(n)+1. Thus for example
B(5)=A5(5)+1. This sequence B is not equal to A5, because B(5) is not equal to A5(5). Thus B is
not equal to An for any n, so a computer program for this sequence B does not occur at all in
the infinite list of calculable computer programs. So the sequence B is not calculable.
This proves at once that in reality it is impossible to decide for each program in the list
within a finite space of time whether or not that program belongs to a calculable sequence.
If this were possible, then one could, for each n, effectively find An, calculate An(n), and
calculate B(n), and do all these calculations within a finite space of time.
In short, both formalism and calculism are examples of an exaggerated and stubborn optimism. Their projects are just as impracticable as that medieval project called 'squaring the circle'. This project asks geometricians to construct, with compasses and straight-edge, a rectangle whose area is equal to the area of a circle with radius 1. Thus it asks to construct, with ideal compasses and straight-edge, a line segment of length squareroot(pi), beginning with a line segment of length 1. This is impossible even in heaven (where these ideal tools are available).