Qual è la minimizzazione (μ-funzione) nei tempi di laici?

Question

In Computer Science μ-Function viene utilizzato per estendere il set di funzioni primativamente ricorsive a funzioni generalmente ricorsive, e non riesco a capire cosa fa questa funzione.

Ci sono molte formule, ma non riesco a capire cosa è.Diciamo che sto scrivendo in Python (o da qualsiasi altro linguaggio generale).Quali sono gli esempi di μ-funzione IRL?

Answer 1

Questa è la minimizzazione in Python:

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

.

È un esercizio leggermente più complicato convertire un while in $ \ MU $ , ma essenzialmente, $ \ MU$ esegue una ricerca per il primo ( minimal ) che soddisfa una determinata condizione, in cui non vi è alcuna garanzia che la ricerca avrà successo.