[FOM] Logic and Fibonacci
zahidi at logique.jussieu.fr
Fri Jan 9 04:41:44 EST 2004
Dear John and other FOM members
The Fibonacci numbers were used by Matijasevich to construct a Julia
Robinson predicate, if I remmber correctly. Matijasevich showed that the
relation "x is the n-th Fibonnaci number" is a diophantine relation in x
and n. This together with the work of Davis, Robinson and Putnam led to
the negative solution of Hilbert's Tenth Problem.
In later expositions of the negative solution to Hilbert's Tenth Problem
Fibonacci numbers are replaced by solutions of Pell-equations.
I guess the above is correct, if not, I'm sure Martin Davis will correct
> In, _Algebra in Ancient and Modern Times, _ V.S. Varadarajan writes on
> page 50:
> They (Fibonocci numbers) remained as curiousities till in the 1960's
> they were found to be crucial in certain
> studies in mathematical logic.
> Does any know what he is referring to?
More information about the FOM