Avete a disposizione un alfabeto che comprende solo tre lettere: M, I, U. Potete comporre stringhe con queste lettere a partire da una stringa già presente, ma seguendo queste regole obbligatorie:
(a) Se una stringa termina con una I, si può aggiungere una U; quindi da UMI si ottiene UMIU, o in generale xI → xIU, dove x è una stringa qualunque (anche nulla).
(b) Se una stringa comincia con M, si può raddoppiare la parte dopo la M; quindi da MUMMI si ottiene MUMMIUMMI, o in generale Mx → Mxx.
(c) Se una stringa contiene tre I consecutive, le si possono sostituire con una U; quindi da MIIIM si ottiene MUM, o in generale xIIIy → xUy.
(d) Se una stringa contiene due U consecutive, le si possono togliere; quindi da UUIMI si ottiene IMI, o in generale xUUy → xy.
All’inizio avete solo a disposizione la stringa MI. Quale successione di operazioni è necessaria per arrivare a ottenere la stringa MU?
(trovate un aiutino sul mio sito, alla pagina https://xmau.com/quizzini/p660.html; la risposta verrà postata lì il prossimo mercoledì. Problema presentato da Douglas Hofstadter in Gödel, Escher, Bach.)
Sembrerebbe impossibile,perché utilizzando il teorema (b) e raddoppiando le I di MI non potremmo mai raggiungere un multiplo di 3 e quindi operare la sostituzione del teorema (c).Stessa cosa intervallando con le U date dal teorema (a)
Tra l’altro,fun fact,ti ho scoperto grazie ad una tua recensione ad un libro di Zellini su Amazon,scoprendo poi che hai scritto libri ed hai un blog.Eccomi qua:)
Beh, le U sono irrilevanti nel contesto, basta contare le I :-)
(sì, faccio tante cose nella vita…)