Análisis computable

Una máquina de Turing de tipo 2 es una máquina de Turing con tres cintas: una cinta de entrada, que es de solo lectura; una cinta de trabajo, en la que se puede escribir y de la que se puede leer; y, notablemente, una cinta de salida, que es de "solo adición".

En este contexto, los números reales se representan como secuencias infinitas arbitrarias de símbolos. Estas secuencias podrían representar, por ejemplo, los dígitos de un número real. Dichas secuencias no tienen por qué ser computables ; esta libertad es importante y, desde un punto de vista filosófico, carece de problemas. ^{[ 2 ]} Cabe señalar que los programas que operan sobre estas secuencias sí deben ser computables en un sentido razonable.

En el caso de los números reales, las representaciones decimales o binarias habituales no son apropiadas. En su lugar, se suele utilizar una representación de dígitos con signo sugerida por primera vez por Brouwer: El sistema numérico es de base 2, pero los dígitos son${\displaystyle {\overline {1}}}$(representando${\displaystyle -1}$), 0 y 1. En particular, esto significa${\displaystyle 1/2}$puede representarse como${\displaystyle 0.1}$y${\displaystyle 1.{\overline {1}}}$.

Para comprender por qué la notación decimal es inapropiada, considere el problema de calcular${\displaystyle z=x+y}$dónde${\displaystyle x=0.(3)}$y${\displaystyle y=0.(6)}$y dando el resultado${\displaystyle z}$en notación decimal. El valor de${\displaystyle z}$es o${\displaystyle 0.(9)}$o${\displaystyle 1.(0)}$. Si se diera este último resultado, por ejemplo, entonces un número finito${\displaystyle n}$de dígitos de${\displaystyle x}$se leería antes de elegir el dígito${\displaystyle 1}$antes del punto decimal en${\displaystyle z}$— pero entonces si el${\displaystyle n+1}$dígito de${\displaystyle x}$se redujeron a 2, luego el resultado para${\displaystyle z}$sería incorrecto. De manera similar, la opción anterior${\displaystyle 0.(9)}$para${\displaystyle z}$A veces estaría equivocado. Este es esencialmente el dilema del fabricante de mesas .

Además de los dígitos con signo, existen análogos de las secuencias de Cauchy y los cortes de Dedekind que, en principio, podrían utilizarse en su lugar.

Las funciones computables se representan como programas en una máquina de Turing de tipo 2. Un programa se considera total (en el sentido de función total, a diferencia de función parcial ) si tarda un tiempo finito en escribir cualquier número de símbolos en la cinta de salida, independientemente de la entrada. Un programa total se ejecuta indefinidamente, generando cada vez más dígitos en la salida.

Los resultados sobre la computabilidad asociados con conjuntos infinitos a menudo implican nombres, que son mapas entre esos conjuntos y representaciones recursivas de subconjuntos de los mismos. Un nombre en un conjunto da lugar a una topología sobre ese conjunto , como se explica más adelante .

La computabilidad de tipo 1 es la forma ingenua del análisis computable, en la que se restringen las entradas a una máquina a números computables en lugar de números reales arbitrarios.

La diferencia entre los dos modelos radica en el hecho de que un programa que se comporta bien sobre números computables (en el sentido de ser total) no necesariamente se comporta bien sobre números reales arbitrarios. Por ejemplo, existen funciones computables sobre los números reales computables que asignan algunos intervalos cerrados acotados a intervalos abiertos no acotados. ^{[ 3 ]} Estas funciones no se pueden extender a números reales arbitrarios (sin hacerlas parciales), ya que todas las funciones computables${\displaystyle \mathbb {R} \to \mathbb {R} }$son continuas, y esto violaría el teorema del valor extremo . Dado que ese tipo de comportamiento podría considerarse patológico, es natural insistir en que una función solo debe considerarse total si es total sobre todos los números reales, no solo sobre los computables.

En caso de que uno no esté satisfecho con el uso de máquinas de Turing (por ser de bajo nivel y algo arbitrarias), existe un topos de realizabilidad llamado topos de Kleene -Vesley en el que se puede reducir el análisis computable al análisis constructivo . Este análisis constructivo incluye todo lo que es válido en la escuela de Brouwer, y no solo en la escuela de Bishop . ^{[ 4 ]} Además, un teorema en esta escuela de análisis constructivo es que no todos los números reales son computables , lo cual no es constructivamente equivalente a que existan números incomputables . Esta escuela de análisis constructivo está, por lo tanto, en directa contradicción con las escuelas de análisis constructivo —como la de Markov— que afirman que todas las funciones son computables. En última instancia, muestra que si bien la existencia constructiva implica computabilidad, de hecho no es problemático —e incluso útil— afirmar que no toda función es computable.