Sistemul MIU e introdus de Douglas R. Hofstadter in Gödel, Escher, Bach iar aici am pornit de la prezentarea facuta de Cristian Calude in Adevarat, dar nedemonstrabil (Editura Stiintifica si Enciclopedica, Bucuresti, 1988). Prezentarea sistemului MIU e urmatoarea:
Vocabular: M, I, U
Axioma: MI
Regula 1: La sfarsitul oricarui sir finit de litere care se termina in I se poate adauga un U.
Regula 2: Din Mx se poate deduce Mxx (x este orice secventa finita formata din literele din vocabular)
Regula 3: Grupul III poate fi inlocuit prin U.
Regula 4: Grupul UU poate fi sters, oriunde apare.
Exemplu de demonstratie (fiecare linie e dedusa din linia anterioara):
(1) MI (axioma)
(2) MII (regula 2)
(3) MIIU (regula 1)
(4) MIIUIIU (regula 2)
(5) MIIUIIUIIUIIU (regula 2)
Alt exemplu:
(1) MI (axioma)
(2) MII (regula 2)
(3) MIIII (regula 2)
(4) MIIIIIIII (regula 2)
(5) MIUIIII (regula 3)
(6) MIUUI (regula 3)
(7) MII (regula 4)
Iar acum vine problema. MU este sau nu teorema in sistem?
Înclin să cred că nu. De I-ul pe care îl avem din axiomă nu putem scăpa decât aplicând regula 3, pentru minim 3. Însă nu văd cum am scăpa de toţi I, din moment ce nu-i putem avea decât în puteri de-ale lui 2 (prin regula 2) şi simplifica doar în multipli de 3. Cute, aştept răspunsul 🙂
Rationamentul lui kristache pare sa fie cat se poate de corect.
Noi ne jucam cu lucruri de tipul asta la facultate, la cursul de limbaje formale si automate. Automatele finite lucreaza cu vocabulare si seturi de reguli similare cu cele din post si e destul de impresionant ce se poate obtine cu un set de reguli aparent foarte simple 😉
@kristache: da, numarul de aparitii ale lui I in orice teorema demonstrabila in MIU nu e divizibil cu 3, iar pentru a obtine MU ar trebui sa nu mai avem nici un I.
o alta chestie care mi s-a parut interesanta e ideea de a “aritmetiza” sistemul, inlocuind M, I si U prin numere si formuland regulile sistemului ca reguli aritmetice.
@Doru Barbu: ok, dar la automatele finite (deterministe) nu poti obtine decat un anumit output pentru un input dat (intr-o anumita stare); aici inputul e axioma, dar poti aproape la fiecare pas sa aplici o regula diferita si sa obtii in linia urmatoare o alta teorema;
dar daca tot ai adus vorba, mai e o problema interesanta: exista o procedura algoritmica prin care sa poti spune despre un sir oarecare de simboluri (continand doar literele din vocabular) daca este sau nu teorema in MIU?
Well, ducandu-ma un pic cu gandul la logica matematica din anul I as zice ca demonstratia in cauza s-ar putea realiza dupa cel mult 2n pasi, unde n e numarul de elemente ale arborelui… Okay, it’s a bit fuzzy for me, dar abia am inceput studiul limbajelor formale si inca mai fac corelatii intre ce stiam deja si ce invat acum… O sa studiez problema cand o sa am timp 🙂
2n de mai sus trebuia sa fie 2^n, dar wordpress strip-uie tag-ul 🙁