What is minimization (μ-function) in layman tems?
-
29-09-2020 - |
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?
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