**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Μ operator

Summary

In computability theory, the μ-operator, minimization operator, or unbounded search operator searches for the least natural number with a given property. Adding the μ-operator to the primitive recursive functions makes it possible to define all computable functions.
Suppose that R(y, x1, ..., xk) is a fixed (k+1)-ary relation on the natural numbers. The μ-operator "μy", in either the unbounded or bounded form, is a "number theoretic function" defined from the natural numbers to the natural numbers. However, "μy" contains a predicate over the natural numbers, which can be thought of as a condition that evaluates to true when the predicate is satisfied and false when it is not.
The bounded μ-operator appears earlier in Kleene (1952) Chapter IX Primitive Recursive Functions, §45 Predicates, prime factor representation as:
"" (p. 225)
Stephen Kleene notes that any of the six inequality restrictions on the range of the variable y is permitted, i.e. y < z, y ≤ z, w < y < z, w < y ≤ z, w ≤ y < z and w ≤ y ≤ z. "When the indicated range contains no y such that R(y) [is "true"], the value of the "μy" expression is the cardinal number of the range" (p. 226); this is why the default "z" appears in the definition above. As shown below, the bounded μ-operator "μyy

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (6)

Related courses (24)

Primitive recursive function

In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive.

Μ operator

In computability theory, the μ-operator, minimization operator, or unbounded search operator searches for the least natural number with a given property. Adding the μ-operator to the primitive recursive functions makes it possible to define all computable functions. Suppose that R(y, x1, ..., xk) is a fixed (k+1)-ary relation on the natural numbers. The μ-operator "μy", in either the unbounded or bounded form, is a "number theoretic function" defined from the natural numbers to the natural numbers.

General recursive function

In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis).

COM-502: Dynamical system theory for engineers

Linear and nonlinear dynamical systems are found in all fields of science and engineering. After a short review of linear system theory, the class will explain and develop the main tools for the quali

COM-300: Stochastic models in communication

L'objectif de ce cours est la maitrise des outils des processus stochastiques utiles pour un ingénieur travaillant dans les domaines des systèmes de communication, de la science des données et de l'i

MATH-408: Regression methods

General graduate course on regression methods

Related lectures (229)

Bifurcations: Fold BifurcationCOM-502: Dynamical system theory for engineers

Covers the concept of fold bifurcation in dynamical systems, focusing on the saddle-mode behavior.

Dynamical System Theory: BifurcationsCOM-502: Dynamical system theory for engineers

Covers the topic of bifurcations in dynamical system theory, focusing on the pitchfork bifurcation.

Holography in Classical GravityPHYS-739: Conformal Field theory and Gravity

Covers the concept of holography in classical gravity and its relation to string theory.