La integral, ¿para qué métodos numéricos dará siempre un resultado incorrecto?

Question

Estaba pensando en la siguiente función:

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

Y la siguiente integral definida:

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

Lo sé porque los números computables son contables, $I=1$ .

Sin embargo, ¿tengo razón al suponer que cualquier método numérico dará $I=0$ (debido a la naturaleza computable de cualquier $x$ un ordenador puede crear)?

Answer 1

En el sentido más estricto del término, esa integral es computable porque es igual a $1$ . Las cuestiones de computabilidad son independientes de si un ordenador puede "averiguar" las reducciones necesarias. Si vas a utilizar una integral de Lebesgue, es injusto pedirle al ordenador que haga algo diferente.

En un mundo de pensamiento más difuso, podríamos querer que nuestro algoritmo en realidad realizar una suma de Riemann, en lugar de "Oye, eso $1$ . Voy a salir $1$ ." Si queremos tomar una suma de Riemann para la integral, entonces necesitamos algunos ingredientes:

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

Ahora, dado que los ordenadores no trabajan con números reales, tenemos que averiguar cómo estamos representando un número real, y resulta que esto es crítico . He aquí algunas formas razonables de hacerlo:

Dejemos que $x$ ser representado por alguna caja negra (es decir, otra máquina u oráculo) que pueda escupir dígitos de $x$ de uno en uno, para siempre.

Bueno, ahora $f$ es incalculable porque su primer dígito nunca puede determinarse a partir de un número finito de valores. Por lo tanto, nuestro método numérico no puede hacer nada. Dado que esta es una forma bastante común de modelar el cálculo de funciones sobre los reales, es un poco decepcionante. Y si tuviéramos algún oráculo que nos dijera el valor de $f$ Dado ese flujo de bits entonces -bueno, ahora estamos alimentando una caja negra a otra- y no está claro de dónde sacó nuestro algoritmo todos estos dispositivos mágicos o cómo se supone que debe trabajar con ellos.

Dejemos que $x$ ser representado por una máquina de Turing, que produce los dígitos de un número.

Bien. Ahora $f$ es computable. Oh, excepto que, donde la definición anterior realmente funciona en todo $\mathbb R$ , éste sólo funciona en los números computables. Y $f$ es idéntico a cero en ese dominio - por lo que el hecho de que lo hayamos definido de otra manera en otro lugar es totalmente irrelevante - es es a todos los efectos, la función cero.

Dejemos que $x$ ser representado como algún definición de un número real en algún sistema lógico.

Si dijéramos que podemos representar los reales mediante alguna expresión que defina un valor único, por ejemplo $$x=\sum_{i=0}^{\infty}2^{-BB(i)}$$ donde $BB$ es la función del castor ocupado. Podemos ver rápidamente que un montón de expresiones dan números bien definidos - pero estos números podrían no ser computables, como el de arriba. Por supuesto, estoy casi seguro (pero no puedo demostrarlo sin una definición adecuada) que decidir si una expresión es computable es un problema no computable - así que $f$ es incalculable. Pero si pudiéramos introducir nuestras expresiones en un oráculo que diera como resultado el valor de $f$ , podríamos obtener $0$ o $1$ y no necesariamente obtendría $0$ como la salida de la integral.

Pero no olvidemos un hecho crucial: No hay integral de Riemann para $f$ . ¿Qué espera que hagan los métodos numéricos?

Answer 2

Si estás hablando en términos de integral de Riemann, debes demostrar que $f(x)$ es incluso integrable, lo que no creo que sea. Si estás hablando en términos de integral de Lebesgue, $f(x)=1$ .

Además, ¿qué es un "método numérico"? Tengo un método numérico para ti y es sólo un paso: $\int_0^1 f(x)=1$ . ¿No es un método numérico?

Creo que en general, tu planteamiento será infructuoso porque una integral es un tipo de límite. Y los límites, por definición, tienen esquemas de aproximación.