Funzione 91 di McCarthy

Da Wikipedia, l'enciclopedia libera.

In matematica discreta, la Funzione 91 di McCarthy è una funzione ricorsiva che ritorna 91 per tutti gli argomenti n ≤ 101 e ritorna 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 \le 100\mbox{ } \end{matrix}\right.

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 > 100
M(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 an < 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.


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica