En la teoría de la computabilidad , el operador μ, el operador de minimización o el operador de búsqueda ilimitada buscan el menor número natural con una propiedad determinada. Agregar el operador μ a los cinco operadores recursivos primitivos hace posible definir todas las funciones computables .
Supongamos que R( y , x 1 , ..., x k ) es una relación fija ( k +1)-aria sobre los números naturales . El operador μ "μ y ", ya sea en forma ilimitada o limitada, es una "función teórica de números" definida de los números naturales a los números naturales. Sin embargo, "μ y " contiene un predicado sobre los números naturales que entrega verdadero cuando el predicado se cumple y falso 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:
Stephen Kleene señala que cualquiera de las seis restricciones de desigualdad en el rango de la variable y está permitida, 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 y tal que R( y ) [es "verdadero"], el valor de "μ y"expresión es el número cardinal del rango" (p. 226); esta es la razón por la que 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 denominadas suma finita Σ y producto finito Π, una función de predicado que "hace la prueba" y una función de representación que convierte {t, f} a { 0 , 1 }.
En el Capítulo XI §57 Funciones recursivas generales, Kleene define el operador μ ilimitado sobre la variable y de la siguiente manera,
En este caso, R mismo, o su función de representación , entrega 0 cuando se cumple (es decir, entrega verdadero ); la función luego entrega el número y . No existe un límite superior en y , por lo tanto, no aparecen expresiones de desigualdad en su definición.