Operador μ

En teoría de computabilidad , el operador μ , el operador de minimización o el operador de búsqueda ilimitada buscan el menor número natural con una propiedad dada. Agregar el operador μ a las funciones recursivas primitivas permite definir todas las funciones computables .

Supongamos que R( y , x ₁ , ..., x _k ) es una relación fija ( k + 1)-aria sobre los números naturales . El operador μ "μ y ", ya sea en forma ilimitada o acotada, es una "función teórica de números" definida desde los números naturales hasta los números naturales. Sin embargo, "μ y " contiene un predicado sobre los números naturales, que puede considerarse como una condición que se evalúa como verdadera cuando se satisface el predicado y como falsa cuando no lo es.

El operador μ acotado aparece anteriormente en Kleene (1952) Capítulo IX Funciones recursivas primitivas, §45 Predicados, representación de factores primos como:

" " (pág. 225)${\displaystyle \mu y_{y<z}R(y).\ \ {\mbox{El menor}}\ y<z\ {\mbox{tal que}}\ R(y),\ {\mbox{si}}\ (\existe y)_{y<z}R(y);\ {\mbox{en caso contrario}},\ z.}$

Stephen Kleene señala que se permite cualquiera de las seis restricciones de desigualdad en el rango de la variable y , es decir, y < z , y ≤ z , w < y < z , w < y ≤ z , w ≤ y < z y w ≤ y ≤ z . "Cuando el rango indicado no contiene ninguna y tal que R( y ) [sea "verdadero"], el valor de la expresión "μ y " es el número cardinal del rango" (p. 226); por eso aparece la " z " predeterminada en la definición anterior. Como se muestra a continuación, el operador μ acotado "μ y _{y < z} " se define en términos de dos funciones recursivas primitivas llamadas suma finita Σ y producto finito Π, una función predicada que "hace la prueba" y una función representativa que convierte {t, f} en { 0 , 1 }.

En el Capítulo XI §57 Funciones recursivas generales, Kleene define el operador μ ilimitado sobre la variable y de la siguiente manera:

" " (p. 279, donde " " significa "existe una y tal que...")${\displaystyle (\exists y)\mu yR(y)=\{{\mbox{el menor (número natural)}}\ y\ {\mbox{tal que}}\ R(y)\}}$${\displaystyle (\existe y)}$

En este caso, R mismo, o su función representativa , entrega 0 cuando se satisface (es decir, entrega verdadero ); la función entrega entonces el número y . No existe ningún límite superior en y , por lo tanto, no aparecen expresiones de desigualdad en su definición.

Para un R( y ) dado, el μ-operador ilimitado μ y R( y ) (nótese que no se requiere "(E y )") es una función parcial . Kleene, en cambio, la convierte en una función total (cf. p. 317):

${\displaystyle \varepsilon yR(x,y)={\begin{cases}{\text{el menor }}y{\text{ tal que }}R(x,y),&{\text{si }}(Ey)R(x,y)\\0,&{\text{en caso contrario}}.\end{cases}}}$

La versión total del operador μ ilimitado se estudia en matemáticas inversas de orden superior (Kohlenbach (2005)) en la siguiente forma:

${\displaystyle (\existe \mu ^{2})(\forall f^{1}){\big (}(\existe n^{0})(f(n)=0)\rightarrow f(\mu (f))=0{\big )},}$

donde los superíndices significan que n es de orden cero, f es de primer orden y μ es de segundo orden. Este axioma da lugar al sistema de los cinco grandes ACA ₀ cuando se combina con la teoría básica habitual de las matemáticas inversas de orden superior. ^{[ cita requerida ]}

(i) En el contexto de las funciones recursivas primitivas , donde la variable de búsqueda y del operador μ está acotada, p. ej. y < z en la fórmula siguiente, si el predicado R es recursivo primitivo (Prueba de Kleene n.° E, p. 228), entonces

μ y _{y < z} R( y , x ₁ , ..., x _n ) es una función recursiva primitiva.

(ii) En el contexto de las funciones recursivas (totales) , donde la variable de búsqueda y no está acotada pero se garantiza que existe para todos los valores x _i de los parámetros del predicado recursivo total R,

( x ₁ ),...,( x _n ) (Ey) R( y , x _i , ..., x _n ) implica que μ y R( y , x _i , ..., x _n ) es una función recursiva total .

Aquí ( x _i ) significa "para todo x _i " y E y significa "existe al menos un valor de y tal que..." (cf Kleene (1952) p. 279.)

entonces los cinco operadores recursivos primitivos más el operador μ ilimitado pero total dan lugar a lo que Kleene llamó las funciones recursivas "generales" (es decir, funciones totales definidas por los seis operadores de recursión).

(iii) En el contexto de las funciones recursivas parciales : supongamos que la relación R se cumple si y solo si una función recursiva parcial converge a cero. Y supongamos que esa función recursiva parcial converge (a algo, no necesariamente a cero) siempre que μ y R( y , x ₁ , ..., x _k ) esté definida e y sea μ y R( y , x ₁ , ..., x _k ) o menor. Entonces la función μ y R( y , x ₁ , ..., x _k ) también es una función recursiva parcial.

El operador μ se utiliza en la caracterización de las funciones computables como funciones recursivas μ .

En matemáticas constructivas , el operador de búsqueda ilimitado está relacionado con el principio de Markov .

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

El operador μ acotado se puede expresar 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 adecuado). 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 "la función que representa " del predicado R. La función ψ se define desde las entradas (t = "verdad", f = "falsedad") hasta las 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 booleano OR, y la suma Σ actúa de manera similar a un operador booleano AND 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 la base Σ( x , 0) = 0 y el 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 si se observa con un ejemplo, como el que dio Kleene. Él simplemente inventó las entradas para la función representativa ψ(R( y )). Designó las funciones representativas χ( y ) en lugar de ψ( x , y ):

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

En una nota al pie, Minsky permite que su operador finalice 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. 210)

La razón para el valor cero es que el operador ilimitado μ y se definirá en términos de la función "producto" Π con su índice y permitido para "crecer" a medida que el operador μ busca. Como se señaló 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 una de 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 funciones recursivas parciales , Kleene admite más adelante un tercer resultado: "μ = indeciso". ^[1] )

Kleene divide su definición del operador μ ilimitado 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 debe utilizar una definición, entonces la función teórica de números χ debe producir cero para "satisfacer" el operador μ. Con este asunto resuelto, demuestra con una sola "Prueba III" que 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 una y que satisface (a) μ y ψ( x , y ) o (b) μ y R( x , y ).

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

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

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 la recursión primitiva, pero Kleene no nos ha proporcionado un paso de 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 lo que está pasando, primero tenemos que recordar que hemos asignado un parámetro (un número natural) a cada variable x _i . Segundo, vemos un operador sucesor en funcionamiento iterando y (es decir, y' ). Y tercero, vemos que la función μ y _{y < z} χ( y , x ) solo está produciendo 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 señalar que la línea (iii) representa una salida , una salida que se toma solo cuando la búsqueda encuentra con éxito una y que satisface χ( y ) y el término producto medio π( 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 luego:
• τ( z' , 0, y ) = τ( z' , 0, n ) = n y se realiza la búsqueda del operador μ.

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

Tanto Minsky (1967) p. 21 como Boolos-Burgess-Jeffrey (2002) p. 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 a Minsky sin la "peculiaridad" mencionada en la nota al pie. La demostración utilizará un modelo de máquina contadora "sucesora" 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 denominado "registro de estados" que renombraremos "Registro de Instrucciones" (IR), (ii) unos pocos "registros", cada uno de los cuales puede contener sólo un único 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á (ver 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, al principio, la asignación de un número natural a cada una de sus variables x y una 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 hasta el infinito o hasta que se produzca una coincidencia. Por lo tanto, el registro " y " debe ser ilimitado: debe ser capaz de "almacenar" un número de tamaño arbitrario. A diferencia de un modelo informático "real", los modelos de máquina abstractos lo permiten. En el caso de un operador μ acotado , un operador μ de acotación inferior comenzaría con el contenido de y establecido en un número distinto de cero. Un operador μ de acotación superior requeriría un registro adicional "ub" para contener el número que representa la acotación superior más una operación de comparación adicional; un algoritmo podría prever tanto acotación inferior como superior.

En lo que sigue, 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 " w " dedicado, 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 vea 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 desde 0. Luego, en la instrucción " n +2", el algoritmo evalúa su función φ( x , y ) -- asumimos que esto requiere j instrucciones para lograrse -- 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 escapa a través de exit ; de lo contrario, incrementa el contenido del registro " y " y vuelve a realizar un bucle con este nuevo valor y para probar la función φ( x , y ) nuevamente.

• Formalismo macartista

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 todas y cada una de las combinaciones de valores de sus parámetros x _i algún número natural y satisfará el operador μ de modo que el algoritmo que representa el cálculo pueda terminar:

"...siempre debemos dudar en suponer que un sistema de ecuaciones realmente define una función recursiva general (es decir, total). Normalmente requerimos evidencia auxiliar para esto, por ejemplo en la forma de una prueba inductiva de que, para cada valor de argumento, el cálculo termina con un valor único." (Minsky (1967) p.186)

"En otras palabras, no deberíamos afirmar que una función es efectivamente calculable sobre la base de 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 ver un ejemplo de lo que esto significa en la práctica, vea los ejemplos en mu funciones recursivas —incluso el algoritmo de sustracción 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 incorrecto con el formato 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 sustracción "adecuado" 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 quedamos con 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. Volviendo al punto de Kleene: ¿es nuestra "demostración" (es decir, el algoritmo que es nuestra demostración) lo suficientemente convincente como para ser considerada efectiva ?

Minsky (1967) define el operador μ ilimitado en la página 210, pero con un defecto peculiar: el operador no dará como resultado t = 0 cuando se satisface su predicado (la prueba IF-THEN-ELSE); en lugar de eso, da como resultado 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 _, rk , _z ) }

El operador μ ilimitado también está definido por Boolos-Burgess-Jeffrey (2002) p. 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 número en el registro "r3". Quizás la razón por la que Boolos-Burgess-Jeffrey borra r3 es para facilitar un salto incondicional al bucle ; esto se hace a menudo mediante el uso de un registro dedicado "0" que contiene "0":

• Kleene, Stephen (2009) [1952], Introducción a las metamatemáticas , Holanda Septentrional, ISBN 9780923891572, OCLC  935015457
• Kohlenbach, Ulrich (2005), Higher Order Reverse Mathematics, Reverse Mathematics 2001, Notas de clase en lógica, Cambridge University Press , págs. 281–295, CiteSeerX  10.1.1.643.551 , doi :10.1017/9781316755846.018, ISBN 9781316755846
• Minsky, Marvin L. (1972) [1967], Computación: máquinas finitas e infinitas , Prentice-Hall, ISBN 9780131654495, OCLC  974146753

En las páginas 210-215 Minsky muestra cómo crear el operador μ utilizando el modelo de máquina de registros , demostrando así su equivalencia con las funciones recursivas generales .

• Boolos, George ; Burgess, John ; Jeffrey, Richard (2002), "S6.2 Minimización", Computabilidad y lógica (4.ª ed.), Cambridge University Press, págs. 70-71, ISBN 9780521701464