Il problema di partenza è calcolare la seguente potenza di potenze: \[2^{2^{2^{2^0}}}\] Non essendoci parentesi che suggeriscono la priorità di calcolo, ci si sentirebbe legittimati a partire da sinistra o da destra, ma esiste una regola nell'elevazione a potenza che permette di svolgere un qualunque calcolo del genere. Ovviamente il numero più in basso è la base, mentre tutti gli altri sono esponenti. Ricordato ciò, ecco la regola: \[a^{m^n} = a^{m \cdot n}\] che allora può essere generalizzata nel modo seguente: \[a^{b_1^{b_2^{{\cdots}^b_n}}} = a^{\prod_i^n b_i}\] Questo implica che, se uno qualsiasi dei $b_i$ è nullo, allora il risultato della potenza di potenze, in mancanza di parentesi che inducono priorità nel calcolo, è 1.
Il risultato 16 dovuto alla maggior parte degli algoritmi è frutto della difficoltà nel gestire la potenza di potenze utilizzando una regola che discende direttamente dalla definizione di esponenziale. A questo agiungerei anche la vicinanza tra il pensiero da programmatore e quello ammericano di affrontare un problema di petto, con la prima soluzione in mano, senza ragionare sul problema stesso e sulle definizioni matematiche che lo coinvolgono (tranquilli: ci cado anche io in questo modo di approcciarmi, a volte; l'importante è rendersene conto e poi modificare!).
Visto che ci sono, vi segnalo anche la seconda parte della serie.
Aggiornamento del 7 luglio 2016:
Dopo la pubblicazione iniziale di questo post, seguendo un programma che avevo già in mente di attuare, ho posto la domanda su Quora ed è giunta una risposta di Justin Rising che secondo me presenta un elemento importante: rimanda a una pagina wiki ben fatta (e che mi era colpevolmente sfuggita...) con una fonte come quelle necessarie per validare la dimostrazione:
Bronstein, Ilja Nikolaevič; Semendjajew, Konstantin Adolfovič (1987) [1945]. "2.4.1.1.". In Grosche, Günter; Ziegler, Viktor; Ziegler, Dorothea. Taschenbuch der Mathematik (in German) 1. Translated by Ziegler, Viktor. Weiß, Jürgen (23 ed.). Thun and Frankfurt am Main: Verlag Harri Deutsch (and B. G. Teubner Verlagsgesellschaft, Leipzig). pp. 115–120.
D'altra parte il calcolo dell'espressione può essere svolto anche nel modo seguente:
\[n_0 = 2^{2^{2^{2^0}}} = 2^{n_1}\]
\[n_1 = 2^{2^{2^0}} = 2^{n_2}\]
\[n_2 = 2^{2^0} = 2^{n_3}\]
Quindi
\[n_3 = 2^0 = 1 \Rightarrow n_2 = 2 \Rightarrow n_1 = 4 \Rightarrow n_0 = 16\]
E questo, direi, chiude la faccenda in favore di Juhan!