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 per . 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: Esempi: M(99) = M(M(110)) dato che 99 ≤ 100 = M(100) dato che 110 > 100 = M(M(111)) dato che 100 ≤ 100 = M(101) dato che 111 > 100 = 91 dato che 101 > 100M(87) = M(M(98)) = M(M(M(109))) = M(M(99)) = M(M(M(110))) = M(M(100)) = M(M(M(111))) = M(M(101)) = M(91) = M(M(102)) = M(92) = M(M(103)) = M(93) .... continua = M(99) (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 ((<= n 100) (mc91 (mc91 (+ n 11)))) (t (- n 10)))) Segue la dimostrazione del comportamento descritto della funzione:Per 90 ≤ n < 101, M(n) = M(M(n + 11)) = M(n + 11 - 10), poiché n >= 90 quindi n + 11 >= 101 = M(n + 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, M(n) = M(M(n + 11)) = M(91), per ipotesi, dato che a ≤ n + 11 < a + 11 = 91, per il caso base. 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.