Susumu Hayashi

2006/4/6

Hilbert and Computation
Influences of Hilbert's early algebraic works tohis studies in the foundations of mathematics

A forthcoming paper We are now working on a paper,

S. Hayashi
K. Nakatogawa
2002/01/12

Hilbert Workshop
Keio Univ, Mita, Tokyo

which shows how Hilbert’s
foundational works wereinfluenced in his early algebraic
works, especially by the problemof computation appeared in it.

2006/04/06 version

 We will show that it seems that hisfoundational studies were modeledon his works in invariant theory in1880-90’s.
 We can draw some interesting
conclusions from this interpretation.
 In this talk, we report some specificconclusions among them.

Completeness and Decision
methods of mathematics
 Turing’s observation

If a formal system is formallycomplete, then we have a decision
method for the system via brute force
search.
 Thus, if a theory is undecidable, thenthere is no complete formal system.
1

Susumu Hayashi

2006/4/6

Hao Wang’comments in
Turing’s“Reflections
on Kurt Goedel”
observation

Conclusion 1

If Hilbert had been aware of thisconnection at that time, he would
probably have been more skeptical about
the existence of complete formal systems
in the two cases, since presumably hewould have more Theories ofnumbers
doubt about thesenatural
theories
beingand real numbers
decidable…

 Even existence of decision method ofConclusion 2Conclusion 3

However, it is more likely that decision
methods of mathematics in Hilbert’ssense would be rather restrictive than thedecision methods in Turing’s sense.
 Brute force search would not be“computation” in his sense.
 Thus, Turing’s observation did not applyto his case.

 Problem of computability ormathematics in Turing’s sense would
not affect Hilbert’s conviction ofcompleteness much.
 Reason: He knew existence ofdecision method does not trivialize
mathematics from his experience ininvariant theory.

xconstructivity was Hilbert’s greatconcern.
 The concern was initiated by his
study of invariant theory.

2

Susumu Hayashi

2006/4/6

Conclusion 3 (continued)

Conclusion 4

 It’s is likely that he modeled the On this interpretation, his andproblems of completeness anddecision methods of mathematics
on his experience on the solutionof Gordan problem in 1880’s1890’s.

Hilbert’s first encounter of theproblem of finiteness inmathematics.
When he was an unknown young man, hewas studying invariant theory.
 The central problem of invariant theory at
the time was Gordan’s problem.
 It was 1887… * *Bernays’ some seemingly wiredstatements, which puzzled Hao
Wang, are natural.

1886-87 Lecture notes on invariant
theory (1)Gordan’s problem was to find a kind ofbasis for each effectively given set ofalgebraic formulas. The basis must be afinite set.
 It was solved in special cases, but not for
the general case. Mathematicians weremainly attacking the problem by trying analgorithm giving the solution.
3

Susumu Hayashi

2006/4/6

1886-87 Lecture notes on invariant
theory (2)1886-87 Lecture notes on invariant
theory (3) It resembles the problem to find a Gordan’s method is too complicatedfinite axiom system for a given theory.
 In the winter semester 1886-87, still in
Koenigsberg, Hilbert gave lectures on
the subject.
 He wrote like this…..

for actual computation and can be
carried out only for small cases.
 The important and fundamental
problem is only the finiteness of thesystem.
 Cod Ms. Hilbert 521 p.193, p.194

Hilbert’s solution

Hilbert’s defense

He gave a general solution to the problemin 1888.
 The solution was based on a method which
is not recursive but limiting recursive in thesense of the algorithmic learning theory,
thus was no computable.
 Gordan criticized it as “not mathematics,but theology”

 Hilbert defended his method in a

rather emotional way in a letter to F.
Klein, who is the editor-in-chief ofMath. Ann. in which the paper should
appear and Gordan worked as areviewer of the paper.

4Susumu Hayashi

2006/4/6

Computational solution

Hilbert’s offence Nonetheless, a few year later, he gavea computational solution to the sameproblem based on an entirely different
method known as Nullstellenzsatz.
 The algorithm is now known as
Hilbert’s algorithm in the circle ofcomputer algebra.

Hilbert’s 1893 lectures oninvariant theory

in 2002verison “1893” was mistakenly wrote as 1887

Among literatures in which he mentioned
the affair, 1893 lectures on invariant theoryin Goettingen is especially interesting. Itwas just a few months prior to Cantor’s
letter to him telling the first set theoreticalparadox.
 3 copies kept in Cornell and Goettingen
Math. Institut and English translation has
appeared

Even after establishing his fame, herepeatedly mention on the affair withGordan.
 Axiomatisches Denken, 1920 papers on
proof theory, etc.
 They are all published about 40 years later
after the affair.
 The affair must be very impressive for him.

Three levels of existence theorem

1.
2.

3.

He explains there are 3 levels withexistence theorems
Proving the existence: his firstsolution
Determining how many operations
are needed at the most to carry out
the assertion of the theorem: hissecond solution
Actually carry out the computation

5Susumu Hayashi

2006/4/6

Hilbert’s illustration of the three steps


1.
2.

3.

Assume there is ten consecutive ones
1111111111 in the decimal expansionof π.
First, prove the existence.
Second, find a number N of which
one knows that there are 1111111111
before the Nth decimal of π.
Third, calculate the actual occurrence.

The 2nd level and Turing’s
observation
From Turing’s observation, the second andthird levels are achieved just by brute force
search.
 However, this is not what mathematicians,
especially applied mathematician thinks.
 The second level has a great practical andmathematical importance.
Other evidences of algebraic
infulences
Similarilty of his axiomatics foundations
and Kronecker’s foundations of puremathematics by his ModulTheoire. Ideal
elements = Kronecker’s indeterminates Try and error “learning” process of εsubstituion methods and his first solutionof Gordan problem.
 Etc.etc……


Computation in Hilbert’s sense (1)Modern computer science now knows
Turing’s computation is not computation inreal life. NP-problems etc. are computable
but not non-computable in real life.
 Hilbert knew such a phenomenon as he wasa great calculator in his youth.
 Hilbert’s formula table for his dissertation
*6

Susumu Hayashi

2006/4/6

Computation in Hilbert’s sense (2)Computation in Hilbert’s sense (3) Thus, for him, a decision method A phrase in Hilbert and Ackerkmannof mathematics in Turing’s sense,or even restricted sense, e.g.
primitive recursive one, would be
only “method in principle.”book suggest that they believe adecision method for predicate calculus But, they wrote that practicalapplication of such method might be“illusolich” after its complicatedcomputation steps.

Computation in Hilbert’s sense (4)Other evidences of algebraic
influences We now know even Fermat’s theoremis automatically proved by machines
in principle.
 But, we also know that it does nottrivialize mathematics.
 Hilbert would know this from hisexperience

Similarility of his axiomatics foundations
and Kronecker’s foundations of puremathematics by his ModulTheoire.
 try and error “learning” process of εsubstitution methods and his first solutionof Gordan problem.

7

Susumu Hayashi

2006/4/6

Computation, Algebra, HilbertComputation vs.Laugwitz ignored“sociological” aspects of theConceptual Thoughts
revolution,It’s very likely Hilbert modeled logic on
algebra as he did in 1900’s.
 And, the algebra he was involved is deeply
related to the study of contemporary
computer algebra.
 He believed mathematics very deeply. We
should examine his thoughts from hismathematics, especially, algebra.
D. Laugwtiz andstressed
the revolution
ofso underestimate
set theoryth century
mathematicsandin 19by thestudies
shift
relatedfoundational
which tohadconceptual“sociologically”
andfrom computation
thoughts“technically”
playedthecentral
initiated by Bernhard Riemann.
role in it.
 Hilbert was “Lenin” in the revolution.
 Hilbert’s foundational works should be reexamined from this point of view.
8