Qu'est-ce que la minimisation (fonction μ) en termes simples ?

Question

En informatique, la fonction μ est utilisée pour étendre un ensemble de fonctions primitivement récursives à des fonctions généralement récursives, et je ne comprends pas ce que fait cette fonction.

Il y a beaucoup de formules, mais je n'arrive pas à comprendre de quoi il s'agit.Disons que j'écris en Python (ou tout autre langage à usage général).Quels sont les exemples de fonction μ IRL ?

Answer 1

C'est la minimisation en Python :

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

C'est un exercice légèrement plus compliqué pour convertir un while à $\mu$, mais essentiellement, $\mu$ effectue une recherche du premier (minimal) numéro satisfaisant une condition donnée, pour lequel il n'y a aucune garantie que la recherche aboutisse.