# What is minimization (μ-function) in layman tems?

In Computer Science μ-function is used to extend set of primitively recursive functions to generally recursive functions, and I can't understand what this function does.

There is a lot of formulae, but I can't understand what is is. Let's say I'm writing in Python (or any other general purpose language). What are examples of μ-function IRL?

• It is a while loop. The primitive recursive functions are equivalent to a programming language with only for loops (that is, the number of iterations is fixed). Suppose you hoped to exhibit an even number that is not the sum of two primes. In Python you'd write some kind of "while (sum_of_primes(n)): n=n+1" routine followed by "print(n)". With general recursive functions you'd say something like "answer = mu n[not_sum_of_primes(n)]". Commented Jul 15, 2020 at 10:26
• Thank you! And why is it called 'minimization'? What it minimize? Commented Jul 15, 2020 at 10:31
• What @JimHefferon is getting at is this. As for your actual question, can you re-state the formula? Which parts do you understand, which don't you? Keep in mind that recursion theory is theory; looking at it from a programming perspective may not be helpful. Commented Jul 15, 2020 at 12:24
• I understand that theory wants to use own language, but I don't want to discard years of programming intuition whilst reading the theory. The answer below is good to sooth my programming intuition. Commented Jul 17, 2020 at 15:36

def mu(p):

It is a slightly more complicated exercise to convert a while to $$\mu$$, but essentially, $$\mu$$ performs a search for the first (minimal) number satisfying a given condition, where there is no guarantee that the search will succeed.