Undecidability of the Criterion for Recognizing the Fibonacci Numbers
Alexander Bolotin *
Department of Computer Science, Ben-Gurion University of the Negev, Beersheba, Israel.
*Author to whom correspondence should be addressed.
Abstract
Assuming the conjecture that all effectively calculable functions must be Turing-machine computable, this paper demonstrates that the problem of recognizing Fibonacci numbers must be in general undecidable. This means that there is no algorithm, which in a finite number of steps can correctly decide whether a given positive integer z of arbitrarily large size belongs to the Fibonacci sequence.
Keywords: Fibonacci numbers, golden ratio, Church-Turing thesis, Turing-machine, undecidability