7
$\begingroup$

I was thinking about the following function:

$$f(x) = \begin{cases}0 & x\;\mathrm{computable}\\1&\mathrm{otherwise}\end{cases}$$

And the following definite integral:

$$I = \int_0^1 f(x)\;\mathrm dx$$

I know that since the computable numbers are countable, $I=1$.

However, am I correct in assuming that any numerical method will give $I=0$ (because of the computable nature of any $x$ a computer can create)?

$\endgroup$
4
  • 2
    $\begingroup$ If you want to numerically integrate this function, you must first numerically implement it. How would you do that? $\endgroup$
    – celtschk
    Commented Apr 10, 2015 at 0:03
  • $\begingroup$ @celtschk I hadn't considered that at all. I can see how that would be a problem. I guess any system capable of taking a non-computable number as an input would be "smart" enough to use set theory to evaluate the integral. $\endgroup$
    – k_g
    Commented Apr 10, 2015 at 0:06
  • $\begingroup$ You can't input a number unless you computed it first. How do you plan to compute a non-computable number? $\endgroup$
    – CiaPan
    Commented Apr 10, 2015 at 7:42
  • $\begingroup$ @CiaPan I don't. Which is why I thought any numerical integral would give 0 (I realize this is incorrect now) $\endgroup$
    – k_g
    Commented Apr 11, 2015 at 0:02

2 Answers 2

5
$\begingroup$

In the strictest sense of the term, that integral is computable because it equals $1$. Issues of computability are independent of whether a computer can "figure out" the reductions needed. If you're going to use a Lebesgue integral, it's unfair to ask the computer to do any differently.

In a fuzzier world of thought, we might want our algorithm to actually perform a Riemann sum, rather than "Hey, that $1$. I'm gonna output $1$." If we want to take a Riemann sum for the integral, then we need some ingredients:

  • Some $x$'s
  • Some $f(x)$'s.

Now, given that computers don't actually work with real numbers, we need to figure out how we're representing a real number - and it turns out that this is critical. Here's a few reasonable ways to do it:

Let $x$ be represented by some black box (i.e. another machine or oracle) that can spit out digits of $x$, one at a time, forever.

Well, now $f$ is uncomputable because its first digit can never be determined from finitely many values. So, our numeric method can't do anything. Given that this is a pretty common way to model computation of functions on the reals, that's a little disappointing. And if we had some oracle that told us the value of $f$ given such a stream of bits then - well, now we're feeding one black box into another - and it's unclear where our algorithm got all these magic devices or how it's supposed to work with them.

Let $x$ be represented by a Turing machine, which outputs digits of a number.

Okay. Now $f$ is computable. Oh, except that, where the previous definition really does work on all of $\mathbb R$, this one only works on the computable numbers. And $f$ is identically zero on that domain - so the fact that we defined it otherwise elsewhere is entirely irrelevant - it is, for all intents and purposes, the zero function.

Let $x$ be represented as some definition of a real number in some logical system.

If we said that we might represent reals by some expression defining a unique value - for instance: $$x=\sum_{i=0}^{\infty}2^{-BB(i)}$$ where $BB$ is the busy beaver function. We can quickly see that lots of expressions yield well-defined numbers - but these numbers might not be computable, like the one above. Of course, I'm almost sure (but can't prove without proper definition) that deciding whether an expression is computable is an uncomputable problem - so $f$ is uncomputable. But if we could feed our expressions into an oracle that output the value of $f$, we might get $0$ or $1$, and would not necessarily get $0$ as the output of the integral.

But, let us not forget one crucial fact: There is no Riemann integral for $f$. What do you expect numeric methods to do?

$\endgroup$
5
  • 1
    $\begingroup$ Since the set of computable numbers is countable, and a function with a countable number of discontinuities is Riemann integrable, why would $f$ not have a Riemann integral? $\endgroup$
    – Chappers
    Commented Apr 10, 2015 at 0:15
  • 1
    $\begingroup$ @Chappers $f$ has uncountably many discontinuities. It's discontinuous at all the noncomputable numbers too. $\endgroup$ Commented Apr 10, 2015 at 0:21
  • $\begingroup$ Ah, that's a point. Objection withdrawn, although an obvious next question is whether the function can be fiddled to be integrable. Hopefully (for the sake of our poor human brains) the answer is no. $\endgroup$
    – Chappers
    Commented Apr 10, 2015 at 0:24
  • $\begingroup$ @Chappers eh, human brains are overrated. On the internet, nobody knows you're a questionbot. $\endgroup$
    – k_g
    Commented Apr 10, 2015 at 4:22
  • $\begingroup$ @Meelo thanks, this basically confirms my suspicions that this problem is a lot more complicated than I imagined. I never considered how hard it would be to define a non-computable number data structure. $\endgroup$
    – k_g
    Commented Apr 10, 2015 at 4:24
2
$\begingroup$

If you're talking in terms of Riemann integral, you must show that $f(x)$ is even integrable which I don't think it is. If you're talking in terms of Lebesgue integral, $f(x)=1$.

Furthermore, what is a "numeric method"? I have a numeric method for you and it's only one step: $\int_0^1 f(x)=1$. Is this not a numeric method?

I think in general, your approach will be fruitless because an integral is a type of limit. And limits, by definition, have approximation schemes.

$\endgroup$
1
  • 3
    $\begingroup$ It's definitely not Riemann integrable: the computable numbers are dense so $f$ is discontinuous everywhere. $\endgroup$ Commented Apr 10, 2015 at 0:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .