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.
展开▼
