Funzione 91 di McCarthy
Da Wikipedia, l'enciclopedia libera.
In matematica discreta, la Funzione 91 di McCarthy è una funzione ricorsiva che, applicata reiteratamente a ciascuno degli interi positivi minori di 102 arriva al valore 91. Limitatamente all'insieme degli interi positivi minori di 102 essa, quindi, è un'endofunzione avente un unico punto fisso. Tale funzione fu studiata dall'informatico John McCarthy.
La Funzione 91 di McCarthy è definita
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
Questo è come John McCarthy stesso potrebbe aver scritto la funzione, nel linguaggio di programmazione che lui stesso inventò: Lisp.
(defun mc91 (n)
(cond ((< n 1) (error "Function only defined for positive values of n"))
((<= n 100) (mc91 (mc91 (+ n 11))))
(t (- n 10))))
Questo che segue è un esempio di programma scritto in Java che mostra che l'implementazione in un linguaggio di relativamente basso livello (o uno che usa diversi paradigmi di programmazione) non corrisponde sempre alla spiegazione di un algoritmo:
public class McCarthy
{
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]);
System.out.println("\n Numero: " + n);
if ( n < 0 )
{
System.out.println("\n Non intero positivo");
System.exit(-1);
}
for (int count = 0, recursion_depth = 1; recursion_depth > 0; count++)
{
System.out.println("Number after " + count + " iteration(s): " + n);
if ( n > 100 )
{
n -= 10;
recursion_depth--;
}
else
{
n += 11;
recursion_depth++;
}
}
System.out.println("Numero Finale: " + n);
}
}
