Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Esercizi di Gara della I edizione


  1. Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n (diverso da 0), termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n.

  2. tabular22

  3. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di tex2html_wrap_inline319tex2html_wrap_inline321 , termina la sua esecuzione lasciando sul nastro una sola tex2html_wrap_inline323 se la sequenza iniziale contiene almeno una tex2html_wrap_inline321 , una sola tex2html_wrap_inline327 altrimenti.

  4. tabular32

  5. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di cifre decimali, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene eliminando tutte le cifre 0 alla sinistra della cifra diversa da 0 più a sinistra. Se la sequenza iniziale è composta da sole cifre 0, la macchina deve lasciare sul nastro un solo 0.

  6. tabular43

  7. Una sequenza si dice palindroma se la sua lettura da sinistra verso destra è uguale alla sua lettura da destra verso sinistra. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di tex2html_wrap_inline319tex2html_wrap_inline321 , termina la sua esecuzione lasciando sul nastro la sola sequenza tex2html_wrap_inline369 se la sequenza iniziale è palindroma, la sola sequenza tex2html_wrap_inline371 altrimenti.

  8. tabular55

  9. Indichiamo con tex2html_wrap_inline389 una sequenza del tipo

  10. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo tex2html_wrap_inline389 , con n > 0 e m > 0, termina la sua esecuzione lasciando sul nastro una sola tex2html_wrap_inline319 se n>m, una sola tex2html_wrap_inline321 se m>n, una sola tex2html_wrap_inline407 se n=m.

    tabular71

  11. Indichiamo con tex2html_wrap_inline423tex2html_wrap_inline425 due generiche sequenze formate da tex2html_wrap_inline319tex2html_wrap_inline321 . Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo tex2html_wrap_inline431 , termina la sua esecuzione lasciando sul nastro la sequenza tex2html_wrap_inline369 se tex2html_wrap_inline423tex2html_wrap_inline425 sono uguali, la sequenza tex2html_wrap_inline371 altrimenti.

  12. tabular83

  13. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di tex2html_wrap_inline319tex2html_wrap_inline321 , con almeno una tex2html_wrap_inline321 , termina la sua esecuzione lasciando sul nastro la sequenza di sole tex2html_wrap_inline321 consecutive (cioè non separate da alcuno spazio) che si ottiene da quella iniziale eliminando tutte le tex2html_wrap_inline319 .

  14. tabular95

  15. Dato un numero intero positivo ntex2html_wrap_inline481 è il numero se n è pari, se n è dispari. Ad esempio, tex2html_wrap_inline491 è il numero 3, mentre tex2html_wrap_inline495 è il numero 4. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza composta da n tex2html_wrap_inline319 consecutive (con n > 1), termina la sua esecuzione lasciando sul nastro la sequenza composta da tex2html_wrap_inline481 tex2html_wrap_inline319 consecutive.

  16. tabular107

  17. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di tex2html_wrap_inline319tex2html_wrap_inline321 , termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene da quella iniziale rimpiazzando due o più tex2html_wrap_inline319 consecutive con una sola tex2html_wrap_inline319 e due o più tex2html_wrap_inline321 consecutive con una sola tex2html_wrap_inline321 .

  18. tabular115
     

Soluzioni


Le soluzioni di seguito riportate sono quelle fornite dalla squadra vincitrice della prima edizione della gara, ovvero da F. Benigni e V. Spina, Liceo Scientifico Statale Barsanti e Matteucci, Viareggio (LU)). Le soluzioni sono per la vecchia versione del simulatore delle macchine di Turing, funzionante con le quadruple; il codice a quintuple per il nuovo simulatore può essere facilmente dedotto.

Tutte le macchine di Turing realizzate dalla squadra vincitrice furono infatti giudicate corrette dalla Giuria della prima edizione della gara. Si noti che la Giuria considera una soluzione di un problema corretta se la macchina di Turing corrispondente si comporta correttamente su tutti i nastri di ingresso utilizzati dalla stessa Giuria per provare la macchina. Pertanto le soluzioni di seguito presentate devono essere intese solo come esemplificative. Inoltre la compattezza della soluzione fornita (ovvero il numero di regole utilizzate) non rientra tra i criteri di valutazione della giuria.

tabular129

tabular157
 

 I testi

  I GARA
  II GARA
  III GARA
  IV GARA
  V GARA
  VI GARA
  VII GARA
  VIII GARA
  IX GARA
  GARA ROTARY 2006
  X GARA
  XI GARA
  XII Gara
  XIII Gara
  XIV Gara
  XV Edizione
  XVI Edizione
  XVII Edizione
  XVIII Edizione
  XIX Edizione
(Altri collegamenti...)