All Computable Functions are Continuous

Added 2023-01-14

When the continuous and discrete cross, fireworks appear


WARNING: The below proof is wrong, as someone brought to my attention. This proof on Math/SE is correct though more complicated. Leaving the post up in case people want to try and find my mistake. :)

Wait, what?

I know what you're thinking so let's just get it out of the way.

def f(x):
  return 0 if x < 0 else 1

"There! That's a discontinuous function in python, clearly whatever big-brained math proof you have must be wrong"

Ah, how easily we write x<0x \lt 0. Note that to define a function taking real numbers as input, xx must have infinite precision. We can think of f(x)f(x) as a Turing machine which takes in an infinite bitstring of input digits and outputs another bitstring of digits. For this post, numbers are represented in fixed-point1.

Now consider how a Turing machine "checks" x<0x \lt 0 for x=0x = 0. We feed in an infinite bitstring of zeros, we output 11 if all the inputs are zero... But then either

  1. The machine never halts, as it has to check all the inputs are zero before outputting anything.
  2. After a certain point the machine decides the input is "close enough to zero" and outputs 11.

In the first case f(0)f(0) wouldn't be defined at zero. In the second case, we could change the digits the machine doesn't look at without changing the output (meaning a tiny tweak to the input doesn't change the output... continuity!)

Proof Idea

At some point the Turing machine processing xx has output kk digits of the output, say, after nn steps. In nn steps the machine could (at most) look at the first nn digits of xx, meaning changing any digits of xx beyond the nnth won't change the output.

This is continuity! Any changes to xx smaller than 2n2^{-n} won't change the output.

Proof

Let xRx \in \mathbf{R} and ϵ>0\epsilon > 0. We want to find a δ>0\delta > 0 so that

xy<δ    f(x)f(y)<ϵ|x - y| \lt \delta \implies |f(x)-f(y)| \lt \epsilon

Let kk be large enough that changing any digits after the kkth in f(x)f(x) doesn't change f(x)f(x) by more than ϵ\epsilon.

Let nn be how many steps it takes the Turing machine before having output the first kk digits of the output. Now changing any digits after the nnth in xx won't change the first kk digits of the output, since the machine is only looking at the first nn in order to decide the first kk.

Now translating into ϵδ\epsilon-\delta language: Let δ\delta be small enough that xy|x-y| implies the first nn digits of x,yx,y are the same. This implies the first kk digits of the output will be the same, meaning the outputs change by less than ϵ\epsilon by our definition of kk.

Conclusion

Hopefully I've shaken your faith in infinity and the reals making sense, there's still time to convert to Finitism before judgement day! It isn't too late!

Footnotes

  1. I'm being a bit sloppy when I say xRx \in \mathbf{R}, really I should say x[0,2]x \in [0,2] if I want to use the simple a020+a121+a_0 2^0 + a_12^1 + \dots fixed-point encoding. There are ways to extend fixed-point beyond bounded-intervals, but they aren't of consequence here.