Gara Nazio­na­le di Pro­gram­ma­zio­ne di una MACCHINA DI TURING

Il Liceo Clas­si­co D’Azeglio par­te­ci­pe­rà alla XXV edi­zio­ne del­la Gara Nazio­na­le di Pro­gram­ma­zio­ne del­la Mac­chi­na di Turing orga­niz­za­ta dal Dipar­ti­men­to di Infor­ma­ti­ca dell’Università di Pisa.

La gara nazio­na­le si svol­ge­rà in due fasi: 

1. Pre­se­le­zio­ne, onli­ne, 04/04/2022
2. Gara, pres­so l’Università di Pisa, 14/05/2022 

Le pri­me 3 squa­dre (da due stu­den­ti) clas­si­fi­ca­te rice­ve­ran­no un atte­sta­to di meri­to e un pre­mio in dena­ro del valo­re rispet­ti­va­men­te di €2000, €1400 e €1100. I mem­bri del­le pri­me 5 squa­dre clas­si­fi­ca­te rice­ve­ran­no la pos­si­bi­li­tà di imma­tri­co­lar­si gra­tui­ta­men­te a qual­sia­si facol­tà dell’Università di Pisa.

Non sono richie­ste com­pe­ten­ze infor­ma­ti­che, né la cono­scen­za di lin­guag­gi di pro­gram­ma­zio­ne. Si trat­ta di pura logi­ca appli­ca­ta a sem­pli­ci algo­rit­mi. Per que­sto è aper­ta a tut­ti gli stu­den­ti del D’Azeglio, dal­la quar­ta gin­na­sio alla ter­za liceo! Chiun­que voglia par­te­ci­pa­re, può scri­ve­re una mail al prof. Biol­ca­ti: emanuele.biolcati@liceomassimodazeglio.it 

E’ una vali­da occa­sio­ne per esplo­ra­re le basi dell’informatica e, allo stes­so tem­po, com­pren­de­re in qua­le modo il genio di Alan Turing por­tò alla rea­liz­za­zio­ne del pri­mo com­pu­ter del­la sto­ria capa­ce di decrip­ta­re le comu­ni­ca­zio­ni in codi­ce e con­tri­bui­re così alla vit­to­ria degli Allea­ti nel­la Secon­da Guer­ra Mon­dia­le. 

Ma che cos’è una mac­chi­na di Turing?

Una mac­chi­na di Turing (MdT) è un insie­me di rego­le che defi­ni­sco­no il com­por­ta­men­to di scrit­tu­ra-let­tu­ra su un nastro di input-out­put. Il nastro può esse­re imma­gi­na­to come un nastro di car­ta di lun­ghez­za infi­ni­ta, divi­so in qua­dra­ti­ni det­te cel­le. Ogni cel­la con­tie­ne un sim­bo­lo oppu­re è vuo­ta. Una MdT ha una testi­na che si spo­sta lun­go il nastro leg­gen­do, scri­ven­do oppu­re can­cel­lan­do sim­bo­li nel­le cel­le del nastro. La mac­chi­na ana­liz­za il nastro, una cel­la alla vol­ta, ini­zian­do dal­la cel­la che con­tie­ne il sim­bo­lo più a sini­stra nel nastro. 

Qui per saper­ne di più: http://mdt.di.unipi.it/Documentazione/MiniCorso.aspx

In cosa con­si­ste la gara?

Ecco un esem­pio di que­si­to trat­to dal­la pri­ma edi­zio­ne del­la gara:

Pro­ble­ma 7. Pro­gram­ma­re una Mac­chi­na di Turing che, dato un nastro ini­zia­le con­te­nen­te una sequen­za di A e B , con alme­no una B, ter­mi­na la sua ese­cu­zio­ne lascian­do sul nastro la sequen­za di sole B con­se­cu­ti­ve (cioè non sepa­ra­te da alcu­no spa­zio) che si ottie­ne da quel­la ini­zia­le eli­mi­nan­do tut­te le A.

La cui solu­zio­ne che si richie­de ai par­te­ci­pan­ti (sen­za che la pos­sa­no pro­va­re su un com­pu­ter) è:

Qui si tro­va­no i testi di tut­te le edi­zio­ni: http://mdt.di.unipi.it/TestiGara/IndiceTesti.aspx

E qui il simu­la­to­re onli­ne: https://https—www.turingsimulator.net/