Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Esercizi di Gara della II edizione


Se non specificato altrimenti, negli esercizi le sequenze iniziali si intendono non vuote, ovvero contenenti almeno un simbolo.



  1. Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo k, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se k è un numero pari, la sola sequenza NO altrimenti.
    1. Esempi
      nastro iniziale
      nastro finale
      148
      SI
      2763
      NO


  2. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale contiene la sottosequenza ABA, la sola sequenza NO altrimenti.

  3. Esempi

    nastro iniziale
    nastro finale
    AABAB
    SI
    ABBA
    NO
    BA
    NO


  4. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B di lunghezza dispari, termina la sua esecuzione lasciando sul nastro il simbolo in posizione centrale della sequenza iniziale.
    1. Esempi
      nastro iniziale
      nastro finale
      AABAB
      B
      AAA
      A
      B
      B


  5. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro la sequenza ottenuta rovesciando quella iniziale.
    1. Esempi
      nastro iniziale
      nastro finale
      AABAB
      BABAA
      ABA
      ABA
      A
      A


  6. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di sole A, termina la sua esecuzione lasciando sul nastro una sequenza di A e B intercalate, di lunghezza doppia rispetto alla sequenza iniziale.
    1. Esempi
      nastro iniziale
      nastro finale
      AA
      ABAB
      AAA
      ABABAB
      A
      AB


  7. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza, eventualmente vuota, contenente un numero pari di A, termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale inserendo al centro della stessa la sequenza BB.
  8. Esempi
    nastro iniziale
    nastro finale
    AA
    ABBA
    AAAA
    AABBAA
     
    BB


  9. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A, B e C termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale rimpiazzando ogni sottosequenza ABC con ACB.
  10. Esempi
    nastro iniziale
    nastro finale
    AABCC
    AACBC
    ABCABCA
    ACBACBA
    ACAB
    ACAB


  11. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro una sequenza contenente lo stesso numero di A e lo stesso numero di B della sequenza iniziale, in cui però tutte le A precedono tutte le B.
    1. Esempi
      nastro iniziale
      nastro finale
      ABBAB
      AABBB
      BABAAA
      AAAABB
      AAB
      AAB


  12. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale contiene un numero pari di A e un numero dispari di B, la sola sequenza NO altrimenti.
    1. Esempi
      nastro iniziale
      nastro finale
      ABBAB
      SI
      BBABAA
      NO
      BABA
      NO
      BBB
      SI


  13. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro una sola A se, nella sequenza iniziale, il numero di A è maggiore o uguale del numero di B, una sola B altrimenti.
  14. Esempi
    nastro iniziale
    nastro finale
    ABABA
    A
    BBAA
    A
    BABBA
    B
    BB
    B

 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...)