¿Pueden codificarse todas las operaciones matemáticas con un lenguaje de Turing Complete?

Question

En el instituto de informática me enseñaron Teorema del programa estructurado - que podría implementar cualquier operación matemática usando:

1. Secuencia
2. Selección
3. Iteración

Después de completar un grado en Ciencias de la Computación - podemos expresar lo que se requiere para cualquier función computable más formalmente con Funciones M-recursivas :

1. La constante $0$ función
2. La función de sucesor
3. Selección de parámetros
4. Composición de la función
5. Recursión primitiva
6. El $ \mu $ -operador (busque el más pequeño $x$ de tal manera que...)

Siendo este el conjunto mínimo de axiomas . Traduciendo esto al código que obtenemos:

1. La constante 0
2. Incremento _ + 1
3. Acceso variable x
4. Concatenación de programas y declaraciones _; _
5. Bucles de cuenta atrás for ( x to 0 ) do _ end
6. Mientras que los bucles while ( x != 0 ) do _ end

Pero he venido en busca de pruebas. ¿Cómo sabemos que todo esto cubre todas las funciones computables? ¿Hay alguna rama obvia de las matemáticas para la que esto no esté cubierto? ¿Hay un defecto en el cálculo Lambda donde aún no se cubren las operaciones matemáticas oscuras?

(Observando, por supuesto, que

• El cálculo lambda es un subconjunto de la reescritura del término,
• que Mathematica eligió la escritura de términos en vez del cálculo lambda como su fundamento,
• y los recientes trabajos en Fundaciones univalentes . )

Mi pregunta es: ¿Pueden codificarse todas las operaciones matemáticas con un lenguaje de Turing Complete?

Answer 1

No.

O, como normalmente se expresaría de forma más positiva: Es posible definir matemáticamente las cosas que no son computables .

Por ejemplo, podemos definir la función $$ f(M) = \begin {cases} 1 & \text {if $ M $ is a lambda term that has a normal form} \\ 0 & \text {otherwise} \end {cases} $$ que definitivamente no es computable es esencialmente el problema de la detención.

Definiendo esta función simbólicamente en todos sus sangrientos detalles no es particularmente esclarecedor. Sin embargo, puede hacerse, y el punto crucial que lo hace no computable es que necesitamos expresar una cuantificación sin límites sobre todos los números naturales, para decir "hay (o no) una secuencia de reducción de cierta longitud finita que conduce a una forma normal".

En términos de formalismo, estamos casi allí con el operador de minimización. Pero normalmente se especifica que $ \mu x.E$ no termina si no hay una adecuada $x$ . Para expresar las definiciones matemáticas en general necesitamos una total operador de minimización $ \bar\mu $ que no puede ser expresada de manera computable: $$ \bar\mu x.E(x) = \begin {cases} \text {the smallest $ x \in\mathbb N $ such that $ E(x)=0 $} & \text {if such an $ x $ exists} \\ 0 & \text {otherwise} \end {cases} $$ Si tuviéramos este operador nosotros, seríamos capaces de expresar cada función que es definible en la lógica de primer orden . Pero no puede ser incluido en un lenguaje de programación real, porque no habría una forma general de que una implementación decidiera regresar $0$ aparte de comprobar infinitamente muchos casos.

---

¿Cómo sabemos que todo esto cubre todas las funciones computables?

Este es un ejemplo de La tesis de Church-Turing . Hasta que no tengamos una definición precisa de "función computable", puede decirse que es una cuestión de fe pero es una experiencia práctica que todos los intentos de definir funciones computables han resultado en conceptos equivalentes, al menos aquellos que no resultaron ser considerados insuficientemente expresiva .

En particular, nadie ha propuesto un mecanismo de computación que parezca ser prácticamente realizable y no puede se exprese en (cualquiera de) esos formalismos. Así que normalmente sólo tomamos nuestro formalismo favorito (se ha demostrado que todos ellos son equivalentes con un rigor impecable) como la definición de "computable".

Answer 2

Pero he venido en busca de pruebas. ¿Cómo sabemos que todo esto cubre todo funciones computables?

La hipótesis de la Iglesia-Turista es una creencia. Así que el término comúnmente usado "función computable" es mayormente que lo que puede ser computado en estos modelos de computación.

Por lo que yo entiendo, en el corazón de los modelos clásicos de computación hay un desajuste en la cardinalidad:

Tenemos muchos programas contables (ya sean cadenas finitas o números naturales) e incontables funciones de máquinas (las asignaciones entre las posibles entradas y salidas de una máquina).

Si se decide por un modelo de cálculo en particular, se asignará parte de las funciones de la máquina a los programas. Debido al desajuste en la cardinalidad, hay funciones de máquina sobrantes que no consiguen que se les asigne un programa, estas son las funciones no computables.

Los modelos clásicos de computación entregan las mismas funciones computables, porque comparten ciertas propiedades.

¿Hay alguna rama obvia de las matemáticas para la que esto no esté cubierto? hay una deficiencia en el Cálculo Lambda donde todavía no se cubre
¿Operaciones matemáticas?

Por ejemplo, hay una rama de análisis, análisis computable que tiene su propio modelo de computación. Recuerdo vagamente que la multiplicación de cualquier número real por 3 no es posible en ese modelo.

También hay una conexión entre las matemáticas constructivistas y la teoría de la computación.

Tal vez esta pregunta atraiga a un experto que pueda explicar esto con más detalle.