title: Funzione 91 di McCarthy
text: # 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.
  
  