Question

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?

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top