A. Gödel, Escher, Bach 

Gödel, Escher, Bach: An Eternal Golden Braid, de Douglas Hofstadter a apărut în 1979. Aceasta tratează concepte de logică, matematică, gândire și inteligență artificială, prin referiri la logicianul Kurt Gödel, artistul grafic olandez Maurits Cornelis Escher și compozitorul german Johann Sebastian Bach. Este una dintre cele mai cunoscute cărți de non-ficțiune, a câștigat mai multe premii (Premiul Pulitzer, U.S. National Book Award pentru știință), a fost tradusă în mai multe limbi și chiar a devenit sursa unui curs MIT. În anul apariției, Martin Gardner a prezentat cartea în rubrica sa din Scientific American.

O problemă faimoasă din această carte este MU Puzzle: Se poate obține MU din MI aplicând următoarele reguli?

Regula 1. Dacă secvența se termină cu I, atunci se poate adăuga U la final (e.g., MI devine MIU).

Regula 2. Dacă secvența este de forma Mx, atunci se poate transforma în Mxx, unde x este o secvență oarecare (e.g., MI devine MII sau MIUM devine MIUMIUM).

Regula 3. Trei litere de I consecutive se pot înlocui de o literă U (e.g., MIII devine MU, UIIIU devine UUU).

Regula 4. Două litere U consecutive se pot șterge (e.g., IUUI devine II, MIUU devine MI).

Secvența de litere poate conține doar literele M, I și U (fiecare poate să apară o dată, de mai multe ori, sau să nu apară deloc). Lasăm MU Puzzle ca exercițiu rezolvitorilor (răspunsul se găsește în carte).

Considerând aceleași reguli, care este lungimea maximă a unei secvențe care se poate obține plecând de la o secvență oarecare s de lungime dată n > 1? Răspundeți și argumentați, pentru diferite structuri ale secvenței s.

Sursa: problemă originală (Ruxandra F. Olimid)

Mai multe informații: Martin Gardner despre Gödel, Escher, Bach: An Eternal Golden Braid https://www.jstor.org/stable/24965235?seq=1/subjects#page_scan_tab_contents

Douglas Hofstadter, autorul cărții Gödel, Escher, Bach: An Eternal Golden Braid despre Martin Gardner https://www.scientificamerican.com/article/martin-gardner-hofstadter/

 

A. Gödel, Escher, Bach 

Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter appeared in 1979. It deals with concepts of logic, mathematics, thinking, and artificial intelligence, by referring to logician Kurt Gödel, Dutch graphic artist Maurits Cornelis Escher and German composer Johann Sebastian Bach. It is one of the most famous non-fiction books, has won several awards (the Pulitzer Prize, the U.S. National Book Award for Science), has been translated into several languages and has even become the source of an MIT course. In the year of its appearance, Martin Gardner presented the book in his Scientific American column.

A famous puzzle in this book is the MU Puzzle: Can you get MU from MI by applying the following rules?

Rule 1. If the sequence ends with I, then U can be added at the end (e.g., MI becomes MIU).

Rule 2. If the sequence is Mx, then it can be converted to Mxx, where x is a sequence (e.g., MI becomes MII or MIUM becomes MIUMIUM).

Rule 3. Three consecutive I can be replaced by a letter U (e.g., MIII becomes MU, UIIIU becomes UUU).

Rule 4. Two consecutive U letters can be deleted (e.g., IUUI becomes II, MIUU becomes MI).

The sequence of letters can only contain M, I, and U (each may appear one time, multiple times, or not appear at all). We leave the MU Puzzle as an exercise for you (the answer is in the book).

Considering the same rules, what is the maximum length of a sequence that can be obtained from a sequence s of given length n> 1? Answer and argue for different structures of the s sequence.

Source: original problem (Ruxandra F. Olimid)

More information: Martin Gardner about Gödel, Escher, Bach: An Eternal Golden Braid https://www.jstor.org/stable/24965235?seq=1/subjects#page_scan_tab_contents

Douglas Hofstadter, the author of Gödel, Escher, Bach: An Eternal Golden Braid about Martin Gardner https://www.scientificamerican.com/article/martin-gardner-hofstadter/