Podría ser [matemáticas] \ text {Halts} (f, M): = \ exist n, f ^ n (M) = f ^ {n + 1} (M) [/ math], donde [math] f [ / math] es alguna función en enteros, [math] M [/ math] es el estado inicial y [math] f ^ n (x) [/ math] significa [math] f (f (\ dots (f (x) ) \ dots)) [/ math] con [math] f [/ math] iterado [math] n [/ math] veces.
La parte difícil es construir las [matemáticas] f [/ matemáticas] y [matemáticas] M [/ matemáticas] dado algún modelo de cálculo. [math] f [/ math] podría realizar una transición de una máquina de Turing o realizar una reducción de la expresión lambda o lo que prefiera.
Construiré un [math] f [/ math] para un sistema de reescritura de cadenas sobre palabras binarias. Es el modelo más simple que se me ocurre. Aquí los programas están representados por una lista de reglas de reescritura. Por ejemplo, un programa de una sola regla “reescribir 01 como 10” (o [matemática] 01 \ a 10 [/ matemática]), aplicada repetidamente a la entrada 0 01 1 (en negrita es la siguiente parte para reescribir) podría producir 01 01, luego 10 01 , luego 1 01 0 y devuelve el resultado 1100.
- ¿Cuándo es una función sub o supermultiplicativa?
- ¿Por qué soy bueno en cursos intensivos de programación, pero sigo reprobando en cursos de teoría de informática? ¿Estoy en condiciones de ser ingeniero de software?
- ¿Existe algún software GRATUITO que pueda aumentar mi calidad o aptitud de inteligencia?
- ¿Qué es la función mágica en MATLAB?
- ¿Qué libros de algoritmos y estructuras de datos tratan bien la recursividad?
En primer lugar, considere una gramática [math] a \ to b, c \ to d, \ dots [/ math] donde [math] a, b, c, d, \ dots [/ math] son cadenas binarias de 0 y 1s. Sea [math] N (a) [/ math] el valor de [math] a [/ math], interpretado como una representación binaria de un número. Sea [math] L (a) [/ math] la longitud de la cadena [math] a [/ math]. Defina la función [matemática] H (n, x) = x ~ \ text {mod} ~ 2 ^ n [/ matemática] para tomar los primeros bits [matemáticos] n [/ matemáticos] de un número y [matemática] T (n , x) = x / 2 ^ n [/ math] para soltar los mismos primeros bits [math] n [/ math] en su lugar (tenga en cuenta que esta división se redondea hacia abajo).
Defina la función [matemática] \ text {cambio} (a, b, x) = N (b) + 2 ^ {L (b)} T (L (a), x) [/ matemática] para reescribir la primera [matemática ] L (a) [/ math] bits de [math] x [/ math] con [math] b [/ math].
Definir predicado [matemática] \ text {prefijo} (a, x): = H (L (a), x) = N (a) [/ matemática] para saber si [matemática] x [/ matemática] comienza con los bits de [matemáticas] a [/ matemáticas].
La entrada se interpretará como una representación binaria simple de un número, por lo que [math] M [/ math] realmente no sabe cuánto dura. Es un pequeño problema, si tiene reglas como [math] 000 \ to \ dots [/ math]. Hay muchas formas de resolver el problema, pero podemos salir adelante sin esas reglas.
Ahora que los preparativos están completos, podemos escribir:
[matemáticas] f (x) = \ begin {cases} \ text {change} (a, b, x) & \ text {if} ~ \ text {prefix} (a, x) \\ \ text {change} ( c, d, x) & \ text {if} ~ \ text {prefix} (c, x) \\ \ dots & \ dots \\ H (1, x) + 2f (T (1, x)) & \ texto {if} ~ x \ ne 0 \\ 0 & \ text {de lo contrario} \ end {cases} [/ math]
Si lo desea, [math] f [/ math] podría reducirse aún más a expresiones aritméticas primitivas utilizando una función [math] \ text {if} (x) = 0 ^ x [/ math] que es 1 en 0 y 0 en todas partes más. [math] f [/ math] tampoco necesita ser recursivo: la iteración en [math] \ text {Halts} [/ math] podría usarse para el mismo efecto. Sin embargo, la definición requeriría un poco más de trabajo.
La conclusión es que la afirmación es simple, en el sentido de que implicará un cuantificador, posiblemente sin recursión, solo aritmética básica. Será difícil, en el sentido de que las fórmulas serán enormes para hacer algo interesante. Y podría verse de la manera que desee, dependiendo del modelo de cómputo que elija, siempre que haya una iteración en algún lugar.
