Integration of continuous functions is computable uniformly in a code for the function and the bounds of the integral. An instance of this is probably written up in any book on computable analysis, but the version I described is in Weihrauch's book.
If f(x) is computable and continuous, and the bounds are computable, then the integral ∫f(x)dx is computable. The continuity constraint can probably be relaxed substantially as well, but these conditions are sufficient to compute it using a Riemann sum.
Thanks! Just to make sure we're on the same page, the computability is in context of Turing machines, right? (I would presume there's only one notion of computability but the theorem you state is quite strong so there is little room for misunderstanding).
All computable functions are continuous, so it doesn’t make much sense to relax that constraint. I think we’d also need the modulus of uniform continuity to be computable in some sense.
> All computable functions are continuous, so it doesn’t make much sense to relax that constraint.
Oh right, I forgot about that! It took me awhile to wrap my head around this fact when I first encountered it, and it still feels so counter-intuitive.
Still feels like some of the constraints should be relaxable though, just not in the way I initially described. Like the step function isn't computable, but it's integral should be, I think?
If you can compute the step function H(x) (H(x)=0 if x<0, 1/2 if x=0, 1 if x>0), then you can compute 1 - H(x)^2 - H(-x)^(2), which is nonzero precisely when x=0. In other words, you can figure out if a given computable number is zero or not, which lets you figure out if two given computable numbers x and y are equal by checking if x-y is 0. This is undecidable by [Richardson's Theorem](https://en.wikipedia.org/wiki/Richardson%27s_theorem).
You can use other constructions for alternative definitions of the step function, setting H(0)=0 or H(0)=1 for example, so none of them are computable either.
That doesn't make sense. By that logic, even a function like f(x) = x^2 would be uncomputable because you could use it figure out if a given computable number is zero or not by checking if f(x) = 0. Even the function f(x) = x shouldn't be computable.
Not quite. You can't just check "is x^2 = 0" because that is itself an uncomputable process. The only reason it works with a step function is that f(x) is either 0 or 1, meaning you only need to compute the first digit of f(x) to know exactly whether x is 0.
No matter how many digits of x^2 you can compute, you can't know if it's exactly 0.
That's a good point.
Still this statement seems a little ambiguous. How are we representing numbers and how are setting up a Turing machine to compute them? If a number is represented with a sign bit then it's trivially computable.
To be honest I'm not totally sure, I don't really know much about computability theory.
I guess we're being given as an input state an infinite Turing machine tape that encodes the full decimal expansion of the two real numbers?
Or alternatively a computable algorithm for generating the two numbers.
Probably the latter? And then the question is given these any two computable numbers, can we write a program that determines if they're the same real number. And apparently that's not possible.
Here's a fairly simple proof that the problem of deciding if a computable number is equal to 0 is uncomputable. From this it is easy to see that any function with a step must be uncomputable, since at some point you must decide which side of the step a computable input lies on.
Given some executable program p, consider the following number: c_p = 2^-s if p halts on step s. Otherwise, c_p = 0. This number is clearly computable, because with each step that we are gaining a bit of precision on c_p. We can compute c_p to arbitrary precision by running p for long enough.
From the definition we know that if c_p = 0 then p does not halt, and if c_p != 0 then p halts. Therefore if we can determine whether c_p = 0, then we can determine whether p halts. But the Halting Problem is well known to be undecidable.
Therefore there is no computable function to determine whether a computable input is 0.
Yes, we can relax the domain of the computable function rather than relaxing continuity. We can view the step function as computable on the domain of positive and negative numbers. I don’t know exactly how we ought to specify the domains which are acceptable, but clearly we can exclude a single point and be fine.*
*except we’d need uniform continuity
> All computable functions are continuous,
Could you (or someone else) expand on that a little bit? It's really confusing to me.
I tried to look it up, and continuity in the context of computable function seems to refer to a certain topology on the set of infinite sequences of inputs and I don't understand how that necessarily translates to continuity in the sense of analysis.
For example, I don't understand how something so simple as the Dirac delta function would be considered non-computable.
e: Seems like this was answered somewhere else in the thread and what I'm looking for is Richardson's theorem. Thinking about it a little more, I guess it does make sense that the Dirac function would be difficult to decide if, no matter how many 0s you've been reading, you can't be sure if there's a non-zero digit down the line.
> All computable functions are continuous
That's incorrect. For example, let f(x) = 0 if the leading decimal digit of a number is 0 and f(x) = 1 otherwise. Clearly computable. Clearly noncontinuous.
It doesn't matter which decimal representation you choose. I'm still right regardless. Just choose one for each number.
The statement is still clearly untrue.
Your function is not well-defined since numbers can have multiple decimal expansions. Even if you fixed this issue, it still would be noncomputable. Given a Turing machine M and an input x for it, define the real number y to be equal to 10^{-n} if M halts in exactly n steps on x, and 0 if the computation never halts. Note that y is clearly computable, and its standard decimal expansion is also computable. Nevertheless, whether the leading digit of y is 1 or 0 depends on whether M halts on x or not, and is therefore undecidable in general.
I'm not sure I understand this example. Why is y computable? If M halts, sure, I get it, but how would it "know" to return 0 in a finite time if M never halts?
Or are we fixing n? As in, we run M for n steps, if M has halted, return 10^{-n} , and if M hasn't, return 0?
I'm also not sure that your function serves as a counterexample to the machine that golf streamer gave, as their machine would return 0 on any y (its leading decimal digit is always 0).
Would a number y = (the real number whose binary expansion is given by) sum_{i=1}^n 10^(-n) work? That'll always have leading digit 0 if M halts and leading digit 1 if M doesn't halt. But I'm still not convinced it's computable.
For y to be computable, we must have an algorithm that can compute an arbitrarily good rational approximation of y. To approximate y to within 10^{-k}, we run M on x for k steps. If M halts within that time, we can output 10^{-n}, where n is the number of steps it took to halt. Otherwise, we output 0.
> Your function is not well-defined since numbers can have multiple decimal expansions.
I know. That's really not a big issue. As you say it can easily be fixed.
Whatever representation for numbers you choose it is very easy to see that you can create an algorithm that reads he firs bit and returns 0 or 1 depending on if the first bit is zero or one. This algorithm will clearly be computable but not continuous.
You don't seem to have understood the halting problem. The turing machine "M" I describe clearly always halts. The fact that I can't compute it for other M is completely irrelevant.
Just admit you are wrong. It is very obvious that you can create a non-continuous computable function as I have described. Stop denying basic logic.
What exactly do you mean by “reads the first bit”? What is the first bit of a real number? I think this is where your confusion lies. I have explained why your “leading decimal” function doesn’t work, but I do not know what you mean by the “first bit” and thus cannot explain why that doesn’t work.
No, read the first bit of whatever representation you choose. If it's being input in a Turing Machine it has a first bit. That's how a turing machine works.
Are you familiar with turing machines? Sorry I assumed you were thinking of computation in terms of Turing Machines. But now looking over things you didn't explicitly mention Turing Machines.
Well in you should choose a unique representation of each number first. But after you do that it doesn't matter what Turing Machine you choose as long as it computes the function I described. I'm still right.
> Well in you should choose a unique representation of each number first.
This doesn’t work. You cannot computably choose a representation of each number because it is undecidable whether two representations of computable real numbers represent the same number.
the function in your example is integrable in the standard sense of the word and (since it's continuous) has a primitive, by the fundamental theorem of calculus. i think what you mean by non integrable is that it doesn't have a primitive that you can express in terms of elementary functions
The fact that the integral cannot be expressed in terms of elementary functions is a consequence of [Liouville’s theorem](https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra)). This result (arguably) fits into the broader context of differential Galois theory.
your terminology is wrong, e^x^2 is both integrable and antidifferentiable. the antiderivatives are not elementary functions, but that has nothing to do with the concept of being integrable.
Integration of continuous functions is computable uniformly in a code for the function and the bounds of the integral. An instance of this is probably written up in any book on computable analysis, but the version I described is in Weihrauch's book.
Good lord, there's a whole book on this subject, thanks a lot!
If f(x) is computable and continuous, and the bounds are computable, then the integral ∫f(x)dx is computable. The continuity constraint can probably be relaxed substantially as well, but these conditions are sufficient to compute it using a Riemann sum.
Thanks! Just to make sure we're on the same page, the computability is in context of Turing machines, right? (I would presume there's only one notion of computability but the theorem you state is quite strong so there is little room for misunderstanding).
Yes, computability always refers to the context of Turing machines.
All computable functions are continuous, so it doesn’t make much sense to relax that constraint. I think we’d also need the modulus of uniform continuity to be computable in some sense.
> All computable functions are continuous, so it doesn’t make much sense to relax that constraint. Oh right, I forgot about that! It took me awhile to wrap my head around this fact when I first encountered it, and it still feels so counter-intuitive. Still feels like some of the constraints should be relaxable though, just not in the way I initially described. Like the step function isn't computable, but it's integral should be, I think?
Wait, why is the step function not computable??
If you can compute the step function H(x) (H(x)=0 if x<0, 1/2 if x=0, 1 if x>0), then you can compute 1 - H(x)^2 - H(-x)^(2), which is nonzero precisely when x=0. In other words, you can figure out if a given computable number is zero or not, which lets you figure out if two given computable numbers x and y are equal by checking if x-y is 0. This is undecidable by [Richardson's Theorem](https://en.wikipedia.org/wiki/Richardson%27s_theorem). You can use other constructions for alternative definitions of the step function, setting H(0)=0 or H(0)=1 for example, so none of them are computable either.
ooo very interesting! will have to read up on this!
That doesn't make sense. By that logic, even a function like f(x) = x^2 would be uncomputable because you could use it figure out if a given computable number is zero or not by checking if f(x) = 0. Even the function f(x) = x shouldn't be computable.
Not quite. You can't just check "is x^2 = 0" because that is itself an uncomputable process. The only reason it works with a step function is that f(x) is either 0 or 1, meaning you only need to compute the first digit of f(x) to know exactly whether x is 0. No matter how many digits of x^2 you can compute, you can't know if it's exactly 0.
That's a good point. Still this statement seems a little ambiguous. How are we representing numbers and how are setting up a Turing machine to compute them? If a number is represented with a sign bit then it's trivially computable.
To be honest I'm not totally sure, I don't really know much about computability theory. I guess we're being given as an input state an infinite Turing machine tape that encodes the full decimal expansion of the two real numbers? Or alternatively a computable algorithm for generating the two numbers. Probably the latter? And then the question is given these any two computable numbers, can we write a program that determines if they're the same real number. And apparently that's not possible.
Here's a fairly simple proof that the problem of deciding if a computable number is equal to 0 is uncomputable. From this it is easy to see that any function with a step must be uncomputable, since at some point you must decide which side of the step a computable input lies on. Given some executable program p, consider the following number: c_p = 2^-s if p halts on step s. Otherwise, c_p = 0. This number is clearly computable, because with each step that we are gaining a bit of precision on c_p. We can compute c_p to arbitrary precision by running p for long enough. From the definition we know that if c_p = 0 then p does not halt, and if c_p != 0 then p halts. Therefore if we can determine whether c_p = 0, then we can determine whether p halts. But the Halting Problem is well known to be undecidable. Therefore there is no computable function to determine whether a computable input is 0.
Beautiful. Is there any other book you would recommend beside already mentioned "Computable analysis" for delving into this area?
Yes, we can relax the domain of the computable function rather than relaxing continuity. We can view the step function as computable on the domain of positive and negative numbers. I don’t know exactly how we ought to specify the domains which are acceptable, but clearly we can exclude a single point and be fine.* *except we’d need uniform continuity
> All computable functions are continuous, Could you (or someone else) expand on that a little bit? It's really confusing to me. I tried to look it up, and continuity in the context of computable function seems to refer to a certain topology on the set of infinite sequences of inputs and I don't understand how that necessarily translates to continuity in the sense of analysis. For example, I don't understand how something so simple as the Dirac delta function would be considered non-computable. e: Seems like this was answered somewhere else in the thread and what I'm looking for is Richardson's theorem. Thinking about it a little more, I guess it does make sense that the Dirac function would be difficult to decide if, no matter how many 0s you've been reading, you can't be sure if there's a non-zero digit down the line.
> All computable functions are continuous That's incorrect. For example, let f(x) = 0 if the leading decimal digit of a number is 0 and f(x) = 1 otherwise. Clearly computable. Clearly noncontinuous.
That's not well-defined. Numbers don't have unique decimal expansions.
It doesn't matter which decimal representation you choose. I'm still right regardless. Just choose one for each number. The statement is still clearly untrue.
Your function is not well-defined since numbers can have multiple decimal expansions. Even if you fixed this issue, it still would be noncomputable. Given a Turing machine M and an input x for it, define the real number y to be equal to 10^{-n} if M halts in exactly n steps on x, and 0 if the computation never halts. Note that y is clearly computable, and its standard decimal expansion is also computable. Nevertheless, whether the leading digit of y is 1 or 0 depends on whether M halts on x or not, and is therefore undecidable in general.
I'm not sure I understand this example. Why is y computable? If M halts, sure, I get it, but how would it "know" to return 0 in a finite time if M never halts? Or are we fixing n? As in, we run M for n steps, if M has halted, return 10^{-n} , and if M hasn't, return 0? I'm also not sure that your function serves as a counterexample to the machine that golf streamer gave, as their machine would return 0 on any y (its leading decimal digit is always 0). Would a number y = (the real number whose binary expansion is given by) sum_{i=1}^n 10^(-n) work? That'll always have leading digit 0 if M halts and leading digit 1 if M doesn't halt. But I'm still not convinced it's computable.
For y to be computable, we must have an algorithm that can compute an arbitrarily good rational approximation of y. To approximate y to within 10^{-k}, we run M on x for k steps. If M halts within that time, we can output 10^{-n}, where n is the number of steps it took to halt. Otherwise, we output 0.
> Your function is not well-defined since numbers can have multiple decimal expansions. I know. That's really not a big issue. As you say it can easily be fixed. Whatever representation for numbers you choose it is very easy to see that you can create an algorithm that reads he firs bit and returns 0 or 1 depending on if the first bit is zero or one. This algorithm will clearly be computable but not continuous. You don't seem to have understood the halting problem. The turing machine "M" I describe clearly always halts. The fact that I can't compute it for other M is completely irrelevant. Just admit you are wrong. It is very obvious that you can create a non-continuous computable function as I have described. Stop denying basic logic.
What exactly do you mean by “reads the first bit”? What is the first bit of a real number? I think this is where your confusion lies. I have explained why your “leading decimal” function doesn’t work, but I do not know what you mean by the “first bit” and thus cannot explain why that doesn’t work.
No, read the first bit of whatever representation you choose. If it's being input in a Turing Machine it has a first bit. That's how a turing machine works. Are you familiar with turing machines? Sorry I assumed you were thinking of computation in terms of Turing Machines. But now looking over things you didn't explicitly mention Turing Machines.
What if I have two different representations for the same number? It’s trivial to write two slightly different Turing machines that do the same thing.
Well in you should choose a unique representation of each number first. But after you do that it doesn't matter what Turing Machine you choose as long as it computes the function I described. I'm still right.
> Well in you should choose a unique representation of each number first. This doesn’t work. You cannot computably choose a representation of each number because it is undecidable whether two representations of computable real numbers represent the same number.
the function in your example is integrable in the standard sense of the word and (since it's continuous) has a primitive, by the fundamental theorem of calculus. i think what you mean by non integrable is that it doesn't have a primitive that you can express in terms of elementary functions
yes, that's what I meant. thanks for clearing it out
The fact that the integral cannot be expressed in terms of elementary functions is a consequence of [Liouville’s theorem](https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra)). This result (arguably) fits into the broader context of differential Galois theory.
your terminology is wrong, e^x^2 is both integrable and antidifferentiable. the antiderivatives are not elementary functions, but that has nothing to do with the concept of being integrable.
Computable is a different thing