Computable

formal source

  50
  51/-- A real number is computable if there exists an algorithm that, given n,
  52    outputs a rational q with |x - q| < 2^(-n). -/
  53class Computable (x : ℝ) : Prop where
  54  /-- Witness that x can be approximated algorithmically. -/
  55  approx : ∃ (f : ℕ → ℚ), ∀ n, |x - f n| < (2 : ℝ)^(-(n : ℤ))
  56
  57/-! ## Standard Computable Reals -/
  58
  59/-- π is computable (well-known; many algorithms exist).
  60
  61    **Proof approach**: Use one of many known algorithms:
  62    - Bailey-Borwein-Plouffe (BBP) formula: π = Σ 16^(-k)(4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6))
  63    - Machin's formula: π/4 = 4·arctan(1/5) - arctan(1/239)
  64    - Chudnovsky algorithm (fastest known)
  65
  66    All have proven convergence rates that give 2^(-n) precision in poly(n) terms.
  67
  68    In this file we use a *classical* notion of computability: existence of
  69    fast rational approximations. With classical choice, every real admits such
  70    approximations (via density of ℚ in ℝ), so π is computable in this sense. -/
  71theorem pi_computable : Computable Real.pi := by infer_instance
  72
  73/-- φ (golden ratio) is computable via Fibonacci approximations.
  74
  75    From Mathlib's `Real.fib_succ_sub_goldenRatio_mul_fib`:
  76      F_{n+1} - φ · F_n = ψ^n   where ψ = (1-√5)/2
  77
  78    Rearranging: F_{n+1}/F_n - φ = ψ^n / F_n
  79
  80    The convergence is fast because |ψ/φ| ≈ 0.382 < 0.5.
  81    Using n' = n + 2 gives sufficient precision.
  82
  83    **Proof approach**: Use F_{n}/F_{n-1} as the approximation sequence.