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 de la gama" (p 226.); es por esto que el valor por defecto " z " en la definición anterior. Como se muestra abajo, la acotada μ-operador "μ y Y < z " se define en términos de dos funciones recursivas primitivas llamado la suma finita Σ y Π producto finito, una función de predicado que "hace la prueba" y una función que representa que los conversos {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.