John McCarthy e l'attrazione fatale del 91

Dopo Steve Jobs e Dennis Ritchie, il fatidico mese di ottobre 2011 ci ha portato via un altro grande informatico: l'americano John McCarthy, uno dei padri dell'intelligenza artificiale, inventore del linguaggio di programmazione LISP, nonché premio Turing nel 1971.
Con McCarthy scompare uno dei giganti della ricerca teorica informatica, uno di quelli che hanno fatto davvero la storia della computazione.

Oltre alle sue ricerche pionieristiche sull'intelligenza artificiale (fu lui, nel lontano 1955, il primo ad adoperare la fortunatissima espressione "intelligenza artificiale"), a McCarthy dobbiamo l'invenzione di alcuni concetti oggi fondamentali dell'ambito della programmazione e delle tecnologie informatiche in genere: ad esempio il meccanismo del "garbage collection", ben noto a chiunque abbia scritto programmi per computer, e l'idea di rendere disponibile come servizio la potenza dei calcolatori, un po' come avviene per l'elettricità o l'acqua. Quest'ultimo concetto, proposto da McCarthy già all'inizio degli anni Sessanta, è stato recentemente rivalutato, e si è imposto con successo sotto forma di tecnologie con nomi diversi ("Software as a service", "Cloud computing", ecc.).

Vorrei qui ricordare McCarthy accennando ad una sua curiosa creazione matematica: la cosiddetta "funzione 91" di McCarthy.
La funzione 91 è definita come segue:







Come si può notare, la funzione è ricorsiva: per i valori minori o uguali a 100 la funzione è definita in termini di se stessa (addirittura con una doppia ricorsione).

La particolare definizione ricorsiva ha delle conseguenze molto interessanti. Provate a calcolare il valore della funzione per un qualsiasi n ≤ 101: ebbene, otterrete sempre e comunque 91!

Proviamo con n=100:

Con n=87:

Se proviamo a disegnare il grafico della funzione 91 di McCarthy, otteniamo qualcosa del genere:

E' evidente, nel primo tratto della funzione, corrispondente ai valori di n ≤ 101, che la funzione rimane fissa sul valore 91.
Lo strano comportamento della funzione, che "precipita" sempre sul numero 91 per tutti gli n ≤ 101, è dimostrabile in modo abbastanza semplice, utilizzando il metodo di induzione. Non riporto qui i passi della dimostrazione, che possono essere trovati ad esempio sulla voce di Wikipedia dedicata alla funzione 91.