Why Computable Functions are Continuous

Added 2021-12-04, Modified 2022-03-12

An explanation without fancy computer science or topology


Imagine a turing machine running forever on an infinite input tape of binary digits, and writing to an output tape of binary digits. This defines a computable function f:RRf : \mathbf{R} \to \mathbf{R}.1

We assume all turing machines preform no "tape reversals", i.e. once digit kk is output it cannot be changed later on. If there were arbitrary tape reversals then the halting problem would prevent us from ever knowing when the first kk digits have been output.

Let xRx \in \mathbf{R} and ϵ>0\epsilon > 0. We want a δ>0\delta > 0 so xy<δ|x - y| < \delta implies f(x)f(y)<ϵ|f(x)-f(y)|<\epsilon.

Compute f(x)f(x). at step nn our turing machine has computed knk \le n digits of f(x)f(x) using (at most!) the first nn digits of xx, meaning any yRy \in \mathbf{R} with the first nn digits in common with xx must have the first kk digits of f(y)f(y) equal to f(x)f(x)! 2

Setting kk such that kk-digit agreement implies ϵ\epsilon-closeness, and letting nn be the timestep when we finish computing the first kk digits allows us to define δ\delta small enough so the first nn digits must agree, finally giving us xy<δf(x)f(y)<ϵ|x-y|<\delta \Rightarrow |f(x)-f(y)|<\epsilon.

See also: this confusing stackexchange post.

Footnotes

  1. Technically R\mathbf{R} is only computable numbers (in the output at least, input too if you're defining stuff reasonably (e.g. so computable inverses exist))

  2. The reason f(y)f(y) has also computed kk digits after nn steps is that yy looks the same as xx when restricted to nn timesteps (since the first nn digits agree!), we are assuming "no tape reversals" (after reading more digits of yy we decide to go back and edit the first kk digits) in our argument.