Funzione 91 di McCarthy
# Funzione 91 di McCarthy

In matematica discreta, la Funzione 91 di McCarthy è una funzione ricorsiva che restituisce 91 per tutti gli argomenti n ≤ 101 e restituisce $n-10$ per $n>101$. Limitatamente all'insieme degli interi minori di 102 essa, quindi, è un'endofunzione avente un unico punto fisso. Tale funzione fu ideata dall'informatico John McCarthy.

La Funzione 91 di McCarthy è definita come segue:

    $M(n)=\left\{{\begin{matrix}n-10,&{\mbox{se }}n>100{\mbox{ }}\\M(M(n+11)),&{\mbox{se }}n\leq 100{\mbox{ }}\end{matrix}}\right.$

Esempi:

John McCarthy potrebbe aver scritto in questo modo la funzione, nel linguaggio di programmazione Lisp che lui stesso inventò: :

Segue la dimostrazione del comportamento descritto della funzione: Per 90 ≤ n < 101,

Di conseguenza M(n) = 91 per 90 ≤ n < 101.

Si può usare questo risultato come caso base per induzione su 11 numeri, in questo modo:

Si assuma che M(n) = 91 per a ≤ n < a + 11.

Allora, per ogni n tale che a - 11 ≤ n < a,

Ora per induzione M(n) = 91 per ogni n in questo blocco. I blocchi così considerati sono adiacenti, senza spazi tra di loro, quindi M(n) = 91 per n < 101. Possiamo anche aggiungere n = 101 come caso speciale.

