[FOM] Logic and Fibonacci

[Zahidi Karim]

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 
me.

Best regards

Karim Zahidi


> 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?
>