pith. machine review for the scientific record. sign in
class definition def or abbrev

Computable

show as:
view Lean formalization →

No prose has been written for this declaration yet. The Lean source and graph data below render without it.

generate prose now

formal statement (Lean)

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

used by (17)

From the project-wide theorem graph. These declarations reference this one in their body.

depends on (16)

Lean names referenced from this declaration's body.