Sistema MIU

[nato_pigro1]

Sto leggendo un libro in cui si fa l'esempio di un sistema formale, vi descrivo il sitema:
ci sono delle stringe formate dalle sequenze dei caratteri M, I, U.

assioma (stringa di partenza):
"MI"

le regole di inferenza sono:
1_se la stringa finisce con una "I" vi si può aggiungere una "U" al fondo.
2_se la stringa è del tipo Mx, si può trasformare in Mxx
3_se ci sono tre "I" di seguito si possono trasforamre in "U" (non viceversa)
4_se ci sono due "U" di seguito si possono eliminare
esempi
1_MIUUI ---> MIUUIU, MI ---> MIU,
2_MIUUII ---> MIUUIIIUUII, MIUUU ---> MIUUUIUUU, MUIU ---> MUIUUIU
3_MIII ---> MU, MUIIUIII ---> MUIIUU, MUIUIUIU ---> non si può perchè non sono di seguito
4_MIUU ---> MI, MUUU ---> MU, MIUUI --->MII

esempio: devo dimostrare "MUUIU"
MI -> MII -> MIIII -> MUI -> MUIU -> MUIUUIU -> MUIIU -> MUIIUUIIU -> MUIIIIU -> MUUIU

ora, lo scopo del gioco è dimostrare (ricavare) "MU", quindi partendo dall stringa "MI" e usando le varie regole di inferenza.
Oppure dimostrare, in qualche modo, che "MU" non si può ricavare.

Nel libro la soluzione c'è, però siccome l'ho appena iniziato (e non si sa quando darà la soluzione) ve lo voglio proporre, io c'ho provato un po', non ci sono riuscito ma mi sembra carino...
se non doveste riuscirci vi prometto che appena so la soluzione ve la dico

[TomSawyer1]

Stai leggendo geb, si capisce.

La stringa può diventare MU solo se si ha una stringa del tipo MIII o MIIIIIIIII, ma questo è impossibile, perché il numero di I consecutivi sarà sempre un numero pari.

[nato_pigro1]

"Crook":Stai leggendo geb, si capisce.

La stringa può diventare MU solo se si ha una stringa del tipo MIII o MIIIIIIIII, ma questo è impossibile, perché il numero di I consecutivi sarà sempre un numero pari.

si
intuitivamente è quello che pensavo pure io, una potenza di 2 non sarà mai multiplo di 3...
ma visto che tu l'hai letto, dopo ci sarà una dimostrazione di ciò o no?

[TomSawyer1]

Sì, c'è più avanti. Ma la dimostrazione è proprio quello che ho detto.