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?

  • 2
    $\begingroup$ 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)]". $\endgroup$ Commented Jul 15, 2020 at 10:26
  • $\begingroup$ Thank you! And why is it called 'minimization'? What it minimize? $\endgroup$ Commented Jul 15, 2020 at 10:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jul 15, 2020 at 12:24
  • $\begingroup$ 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. $\endgroup$ Commented Jul 17, 2020 at 15:36

1 Answer 1


This is minimization in Python:

def mu(p):
    n = 0
    while not p(n):
        n += 1
    return n

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.