operador mu

En lo siguiente , x representa la cadena x _i , ..., x _n .

El operador μ acotado puede expresarse de forma bastante sencilla en términos de dos funciones recursivas primitivas (en adelante, "prf") que también se utilizan para definir la función CASE: el producto de términos Π y la suma de términos Σ (véase Kleene #B, página 224). (Según sea necesario, cualquier límite para la variable, como s ≤ t o t < z , o 5 < x < 17, etc., es apropiado). Por ejemplo:

• Π _{s ≤ t} f _s ( x , s ) = f ₀ ( x , 0) × f ₁ ( x , 1) × ... × f _t ( x , t )
• Σ _{t < z} g _t ( x , t ) = g ₀ ( x , 0) + g ₁ ( x , 1) + ... + g _z-1 ( x , z -1)

Antes de continuar, necesitamos introducir una función ψ llamada " función representativa " del predicado R. La función ψ se define a partir de entradas (t = "verdad", f = "falsedad") y salidas (0, 1) (¡ nótese el orden! ). En este caso, la entrada a ψ, es decir, {t, f}, proviene de la salida de R:

• ψ(R = t) = 0
• ψ(R = f) = 1

Kleene demuestra que μ y _{y < z} R ( y ) se define de la siguiente manera; vemos que la función producto Π actúa como un operador OR booleano, y la suma Σ actúa de forma similar a un AND booleano, pero produce {Σ≠0, Σ=0} en lugar de solo {1, 0}:

μ y _{y < z} R ( y ) = Σ _{t < z} Π _{s ≤ t} ψ( R ( x , t , s )) =

[ψ( x , 0, 0)] +

[ψ( x , 1, 0) × ψ( x , 1, 1)] +

[ψ( x , 2, 0) × ψ( x , 2, 1) × ψ( x , 2, 2)] +

... +

[ψ( x , z -1, 0) × ψ( x , z -1, 1) × ψ( x , z -1, 2) × . . . × ψ ( x , z -1, z -1)]

Nótese que Σ es en realidad una recursión primitiva con base Σ( x , 0) = 0 y paso de inducción Σ( x , y +1) = Σ( x , y ) + Π( x , y ). El producto Π también es una recursión primitiva con paso base Π( x , 0) = ψ( x , 0) y paso de inducción Π( x , y +1) = Π( x , y ) × ψ( x , y +1).

La ecuación es más fácil de observar con un ejemplo, como el que da Kleene. Simplemente inventó las entradas para la función representativa ψ( R ( y )). Designó las funciones representativas χ( y ) en lugar de ψ( x , y ):

El operador μ no acotado —la función μ y— es el que se define comúnmente en los textos. Pero el lector podría preguntarse por qué el operador μ no acotado busca una función R ( x , y ) que dé como resultado cero , en lugar de algún otro número natural.

En una nota al pie, Minsky permite que su operador termine cuando la función interna produce una coincidencia con el parámetro " k "; este ejemplo también es útil porque muestra el formato de otro autor:

"Para μ _t [φ( t ) = k ]" (pág. 210)

La razón del cero es que el operador no acotado μ y se definirá en términos de la función "producto" Π, cuyo índice y puede "crecer" a medida que el operador μ realiza la búsqueda. Como se observa en el ejemplo anterior, el producto Π _{x < y} de una cadena de números ψ( x , 0) *, ..., * ψ( x , y ) da como resultado cero siempre que uno de sus miembros ψ( x , i ) sea cero:

Π _{s < y} = ψ( x , 0) * , ..., * ψ( x , y ) = 0

si cualquier ψ( x , i ) = 0 donde 0≤ i ≤ s . Por lo tanto, Π actúa como un AND booleano.

La función μ y produce como "salida" un único número natural y = {0, 1, 2, 3, ...}. Sin embargo, dentro del operador pueden aparecer dos "situaciones": (a) una "función de teoría de números" χ que produce un único número natural, o (b) un "predicado" R que produce {t = verdadero, f = falso}. (Y, en el contexto de las funciones recursivas parciales , Kleene admite más adelante un tercer resultado: "μ = indeciso". ^{[ 2 ]} )

Kleene divide su definición del μ-operador no acotado para manejar las dos situaciones (a) y (b). Para la situación (b), antes de que el predicado R ( x , y ) pueda servir en una capacidad aritmética en el producto Π, su salida {t, f} debe ser primero "operada" por su función representativa χ para producir {0, 1}. Y para la situación (a), si se va a usar una definición, entonces la función teórica de números χ debe producir cero para "satisfacer" el μ-operador. Una vez resuelto este asunto, demuestra con una sola "Prueba III" que cualquiera de los tipos (a) o (b) junto con los cinco operadores recursivos primitivos producen las funciones recursivas (totales) , con esta condición para una función total :

Para todos los parámetros x , se debe proporcionar una demostración para mostrar que existe un y que satisface (a) μ y ψ( x , y ) o (b) μ yR ( x , y ).

Kleene también admite una tercera situación (c) que no requiere la demostración de "para todo x existe un y tal que ψ( x , y ).". Utiliza esto en su demostración de que existen más funciones recursivas totales de las que se pueden enumerar; cf. nota al pie Demostración de la función total .

La demostración de Kleene es informal y utiliza un ejemplo similar al primero, pero primero transforma el operador μ en una forma diferente que utiliza el "producto de términos" Π que opera sobre la función χ y produce un número natural n , que puede ser cualquier número natural, y 0 en el caso en que se "satisfaga" la prueba del operador μ.

La definición reformulada con la función Π:

μ y _{y < z} χ( y ) =

• (i): π( x , y ) = Π _{s < y} χ( x , s )
• (ii): φ( x ) = τ(π( x , y ), π( x , y' ), y )
• (iii): τ( z' , 0, y ) = y ;τ( u , v , w ) no está definido para u = 0 o v > 0.

Esto es sutil. A primera vista, las ecuaciones parecen utilizar recursión primitiva. Pero Kleene no nos ha proporcionado un paso base y un paso de inducción de la forma general:

• paso base: φ(0, x ) = φ( x )
• paso de inducción: φ(0, x ) = ψ(y, φ(0, x ), x )

Para ver qué está pasando, primero debemos recordar que hemos asignado un parámetro (un número natural) a cada variable x _i . Segundo, vemos un operador sucesor en funcionamiento que itera sobre y (es decir, y' ). Y tercero, vemos que la función μ y _{y < z} χ( y , x ) simplemente produce instancias de χ( y , x ) es decir χ(0, x ), χ(1, x ), ... hasta que una instancia produce 0. Cuarto, cuando una instancia χ( n , x ) produce 0, hace que el término medio de τ, es decir v = π( x , y' ) produzca 0. Finalmente, cuando el término medio v = 0, μ y _{y < z} χ( y ) ejecuta la línea (iii) y "sale". La presentación de Kleene de las ecuaciones (ii) y (iii) se ha intercambiado para dejar claro que la línea (iii) representa una salida , una salida que se toma solo cuando la búsqueda encuentra con éxito un y que satisface χ( y ) y el término de producto intermedio π( x , y' ) es 0; el operador entonces termina su búsqueda con τ( z' , 0, y ) = y .

τ(π( x , y ), π( x , y' ), y ), es decir:

• τ(π( x , 0), π( x , 1), 0),
• τ(π( x , 1), π( x , 2), 1)
• τ(π( x , 2), π( x , 3), 2)
• τ(π( x , 3), π( x , 4), 3)
• ... hasta que se produzca una coincidencia en y = n y entonces:
• τ( z' , 0, y ) = τ( z' , 0, n ) = n y se realiza la búsqueda del operador μ.

Por ejemplo, Kleene "...considera cualquier valor fijo de ( x _i , ..., x _n ) y escribe simplemente 'χ( y )' para 'χ( x _i , ..., x _n ), y )'":

Tanto Minsky (1967) pág.  21 como Boolos-Burgess-Jeffrey (2002) págs.  60-61 proporcionan definiciones del operador μ como una máquina abstracta ; véase la nota al pie Definiciones alternativas de μ .

La siguiente demostración sigue el método de Minsky sin la "peculiaridad" mencionada en la nota al pie. La demostración utilizará un modelo de máquina contadora "sucesor" estrechamente relacionado con los axiomas de Peano y las funciones recursivas primitivas . El modelo consta de (i) una máquina de estados finitos con una TABLA de instrucciones y un llamado "registro de estado" que renombraremos como "Registro de Instrucciones" (RI), (ii) algunos "registros", cada uno de los cuales puede contener solo un número natural, y (iii) un conjunto de instrucciones de cuatro "comandos" descritos en la siguiente tabla:

En lo que sigue, el simbolismo "[ r ] " significa "el contenido de", y "→r " indica una acción con respecto al registro r.

El algoritmo para el operador de minimización μ y [φ( x , y )] creará, en esencia, una secuencia de instancias de la función φ( x , y ) a medida que aumenta el valor del parámetro y (un número natural); el proceso continuará (véase la Nota † a continuación) hasta que se produzca una coincidencia entre la salida de la función φ( x , y ) y algún número preestablecido (normalmente 0). Por lo tanto, la evaluación de φ( x , y ) requiere, en primer lugar, la asignación de un número natural a cada una de sus variables x y la asignación de un "número de coincidencia" (normalmente 0) a un registro " w ", y un número (normalmente 0) al registro y .

Nota †: El operador μ ilimitado continuará este proceso de intento de coincidencia indefinidamente o hasta que se produzca una coincidencia. Por lo tanto, el registro " y " debe ser ilimitado; debe poder "almacenar" un número de tamaño arbitrario. A diferencia de un modelo de computadora "real", los modelos de máquinas abstractas permiten esto. En el caso de un operador μ limitado , un operador μ con límite inferior comenzaría con el contenido de y establecido en un número distinto de cero. Un operador μ con límite superior requeriría un registro adicional "ub" para contener el número que representa el límite superior más una operación de comparación adicional; un algoritmo podría proporcionar límites tanto inferiores como superiores.

A continuación, asumimos que el Registro de Instrucciones (IR) encuentra la rutina μ y en la instrucción número n . Su primera acción será establecer un número en un registro dedicado " w ", un ejemplo del número que la función φ( x , y ) debe producir antes de que el algoritmo pueda terminar (clásicamente, este es el número cero, pero consulte la nota al pie sobre el uso de números distintos de cero). La siguiente acción del algoritmo en la instrucción n + 1 será borrar el registro y ; " y " actuará como un contador ascendente que comienza en 0. Luego, en la instrucción n +2, el algoritmo evalúa su función φ( x , y ) (suponemos que esto requiere j instrucciones) y, al final de su evaluación, φ( x , y) deposita su salida en el registro φ. En la instrucción ( n + j +3) el algoritmo compara el número en el registro " w " (por ejemplo, 0) con el número en el registro " φ - si son iguales el algoritmo ha tenido éxito y sale a través de exit ; de lo contrario incrementa el contenido del registro " y " y vuelve al bucle con este nuevo valor de y para probar la función φ( x , y ) de nuevo.

Lo que es obligatorio para que la función sea una función total es una demostración mediante algún otro método (por ejemplo, inducción ) de que para cada combinación de valores de sus parámetros x _i algún número natural y satisfará el operador μ de manera que el algoritmo que representa el cálculo pueda terminar:

«...siempre debemos ser cautelosos al asumir que un sistema de ecuaciones define realmente una función recursiva general (es decir, total). Normalmente requerimos evidencia auxiliar para ello, por ejemplo, en forma de una prueba inductiva que demuestre que, para cada valor de argumento, el cálculo finaliza con un valor único.» (Minsky (1967) p. 186)

"En otras palabras, no debemos afirmar que una función es efectivamente calculable basándonos en que se ha demostrado que es recursiva general (es decir, total), a menos que la demostración de que es recursiva general sea efectiva." (Kleene (1952) p. 319)

Para un ejemplo de lo que esto significa en la práctica, vea los ejemplos en Función recursiva general : incluso el algoritmo de resta truncada más simple " x - y = d " puede producir, para los casos indefinidos cuando x < y , (1) ninguna terminación, (2) ningún número (es decir, algo con el formato incorrecto, por lo que el resultado no se considera un número natural), o (3) engaño: números incorrectos en el formato correcto. El algoritmo de resta "correcto" requiere una atención cuidadosa a todos los "casos".

( x , y ) = {(0, 0), ( a , 0), (0, b ), ( a ≥ b , b ), ( a = b , b ), ( a < b , b )}.

Pero incluso cuando se ha demostrado que el algoritmo produce el resultado esperado en los casos {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, nos queda una sensación de inquietud hasta que podamos idear una "demostración convincente" de que los casos ( x , y ) = ( n , m ) producen todos los resultados esperados. Como señala Kleene: ¿es nuestra "demostración" (es decir, el algoritmo que constituye nuestra demostración) lo suficientemente convincente como para considerarse eficaz ?

El operador μ no acotado es definido por Minsky (1967) pág.  210 pero con un defecto peculiar: el operador no producirá t = 0 cuando se satisfaga su predicado (la prueba IF-THEN-ELSE); en cambio, produce t = 2. En la versión de Minsky, el contador es " t ", y la función φ( t , x ) deposita su número en el registro φ. En la definición habitual de μ, el registro w contendrá 0, pero Minsky observa que puede contener cualquier número k . El conjunto de instrucciones de Minsky es equivalente al siguiente, donde "JNE" = Saltar a z si no es igual:

{ CLR ( r ), INC ( r ), JNE ( r _j , r _k , z ) }

El operador μ no acotado también es definido por Boolos-Burgess-Jeffrey (2002) págs.  60-61 para una máquina contadora con un conjunto de instrucciones equivalente al siguiente:

{ CLR (r), INC (r), DEC (r), JZ (r, z), H }

En esta versión, el contador "y" se llama "r2", y la función f( x , r2) deposita su valor en el registro "r3". Quizás la razón por la que Boolos-Burgess-Jeffrey borra r3 sea para facilitar un salto incondicional al bucle ; esto se suele hacer mediante el uso de un registro dedicado "0" que contiene "0".