Топ-100
Indietro

ⓘ Funzione 91 di McCarthy. In matematica discreta, la Funzione 91 di McCarthy è una funzione ricorsiva che ritorna 91 per tutti gli argomenti n ≤ 101 e ritorna n ..




                                     

ⓘ Funzione 91 di McCarthy

In matematica discreta, la Funzione 91 di McCarthy è una funzione ricorsiva che ritorna 91 per tutti gli argomenti n ≤ 101 e ritorna n − 10 {\displaystyle n-10} per n > 101 {\displaystyle n> 101}. Limitatamente allinsieme degli interi minori di 102 essa, quindi, è unendofunzione avente un unico punto fisso. Tale funzione fu ideata dallinformatico John McCarthy.

La Funzione 91 di McCarthy è definita come segue:

M n = { n − 10, se n > 100 M n + 11), se n ≤ 100 {\displaystyle Mn=\left\\right.}

Esempi:

M99 = MM110) dato che 99 ≤ 100 = M100 dato che 110 > 100 = MM111) dato che 100 ≤ 100 = M101 dato che 111 > 100 = 91 dato che 101 > 100 M87 = MM98) = MMM109) = MM99) = MMM110) = MM100) = MMM111) = MM101) = M91 = MM102) = M92 = MM103) = M93. continua = M99 come sopra = 91

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

defun mc91 n cond = 90 quindi n + 11 > = 101 = Mn + 1

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,

Mn = MMn + 11) = M91, per ipotesi, dato che a ≤ n + 11 < a + 11 = 91, per il caso base.

Ora per induzione M n = 91 per ogni 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.