Edizione XVII – Problema 1

Cambio di casacca

Nel Mondo dei Programmatori, la vita politica è molto intensa e piena di sorprese.
Nuove liste e partiti si formano e dissolvono di continuo, mentre i Programmatori discutono di quale sia il linguaggio migliore da utilizzare.

Per esempio, fino a qualche anno fa si contavano vari movimenti:

• i Programmatori C Indipendenti (simbolo: c),
• i Discreti & Continui (simbolo: d),
• i Programmatori Strutturalisti (simbolo: s)
• e i Programmatori Lisp Integralisti (simbolo: l).

Negli anni, questi raggruppamenti hanno cambiato molte volte nome, al punto che si è preferito numerarli per chiarezza.

Così,

• i Programmatori C Indipendenti sono diventati il partito 0,
• i Discreti & Continui sono diventati il partito 1,
• i Programmatori Strutturalisti sono diventati il partito 2,
• e i Programmatori Lisp Integralisti il partito 3.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro una stringa sull’alfabeto {c, d, s, l}, in cui ogni simbolo rappresenta un elettore del corrispondente partito, lasci sul nastro gli stessi elettori, codificati però sull’alfabeto {0, 1, 2, 3}.

Diagramma di stato

• Nello stato 0 attraversa tutto l’input
• Per ogni lettera C D S L scrive la codifica corrispondente 0 1 2 3

Tabella delle transizioni di stato

Quintuple #1

(0, C, 0, 0, >)
(0, D, 0, 1, >)
(0, S, 0, 2, >)
(0, L, 0, 3, >)
(0, -, H, -, <)

Quintuple #2

(0, CDSL, 0, 0123, >)