Undecidability of the Criterion for Recognizing the Fibonacci Numbers
Journal of Advances in Mathematics and Computer Science · pp. 1–6 · Published 14 Aug 2015
10.9734/BJMCS/2015/19785Abstract
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.
Cited by 1
A. Bolotin · 2015
Related research
- Closed Formulas for the Sums of Cubes of Generalized Fibonacci Numbers: Closed Formulas of Σn k=0W3 Σ k and n k=1W3 — shares topic coverage
- Some Properties of Generalized Fibonacci Numbers: Identities, Recurrence Properties and Closed Forms of the Sum Formulas ∑nk=0 xkWmk+j — shares topic coverage
- On Summing Formulas for Horadam Numbers — shares topic coverage
- Closed Formulas for the Sums of Squares of Generalized Fibonacci Numbers — shares topic coverage
- A Study on the Sums of Squares of Generalized Fibonacci Numbers: Closed Forms of the Sum Formulas Σn k=0 kxkW2 k and Σn k=1 kxkW2- k — shares topic coverage
Article metrics
Real usage data collected on this platform.
31
Page views
0
PDF downloads
3
Outbound clicks
1
Citations
Views over time
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
Traffic sources
Referring site, by host.
Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.