Macchina di Turing

[_Tipper]

Qualcuno saprebbe farmi vedere come si fa quest'esercizio? Io non saprei proprio dove andare a mettere le mani...

Costruire la Macchina di Turing che produce, a partire da w, la stringa w''=w'#w dove w' è il numero dei bit uno di w. Se non ci sono bit uno w'=0.
Esempio:
Se w=110101101 allora si avrà w''=110#110101101
Se w=00000000 allora si avrà w''=0#00000000

Grazie

[Barnaba1]

Premetto che questo programma funziona se il numero di uno è minore di 10, volendo è fattibile lo stesso, si complica un po di piu la parte di conversione in binario. Premetto inoltre che era già un po che non facevo esercizi con la macchina di Turing per cui il programma si puo sicuramente migliorare (soprattutto ci sono molti stati che sicuramente si potevano evitare). Sostanzialmente è diviso in 3 parti:
1) conteggio del numero di 1
2) conversione in binario del numero di 1
3) formattazione del nastro (secondo me la cosa piu pallosa perche va tenuta presente durante tutto il programma)

#conteggio del numero di 1
0,01,0,01,<
0,-,init,=,>
init,1,inc,u,<
init,0,init,z,>
inc,=uz,inc,=uz,<
inc,-012345678,rip,1123456789,>
rip,=uz,rip,=uz,>
rip,01,init,01,-
rip,-,init,-,-
init,-,code,*,<

#conversione in binario
code,=0123456789uz,code,=0123456789uz,<
code,-,codifica,#,>
codifica,2468,resto0,1234,<
resto0,#01,resto0,#01,<
resto0,-,rip2,0,>
codifica,13579,resto1,01234,<
resto1,#01,resto1,#01,<
resto1,-,rip2,1,>
rip2,0123456789#,rip2,0123456789#,>
rip2,=,codifica,=,<
codifica,=,resto0,=,<
codifica,#,formatta,#,>
codifica,0,formatta,-,>

#formattazione
formatta,=,formatta,-,>
formatta,-,formatta,-,>
formatta,u,ripu,-,<
ripu,-,ripu,-,<
ripu,#01,scrivi1,#01,>
scrivi1,-,formatta,1,>
formatta,z,ripz,-,<
ripz,-,ripz,-,<
ripz,#01,scrivi0,#01,>
scrivi0,-,formatta,0,>
formatta,*,w,-,<
w,-01,w,-01,<
w,#,w',#,<
w',01,w',01,<
w',-,apice,=,<
apice,-,doppioapice,',<
doppioapice,-,dw,',<
dw,-,fine,w,-

[_Tipper]

Ti ringrazio per la risposta ma, sinceramente, non mi è molto chiara.
Mi spiego meglio: io sono abituato a scrivere le transizioni di stato in questo modo:

$q_{i}" a "q_{j}" b d"$

dove $q_{i}$ è lo stato in cui si trova la macchina, $"a"$ è il carattere incontrato, $q_{j}$ è lo stato in cui passa la macchina, $"b"$ è il simbolo che viene scritto al posto di $"a"$ (nulla vieta $"b"="a"$), $d$ è la direzione in cui si sposta la testina, e può essere, ovviamente, destra o sinistra.

Potresti spiegarmi la tua notazione?

Grazie

[Barnaba1]

l'annotazione è sostanzialmente quella:
stato in cui si trova, cosa legge,stato in cui va,cosa scrive, direzione

sinceramente io ho sempre usato un simulatore della macchina di turing, quello con cui mi insegnarono alle superiori e non sapevo che esistesse un altro tipo di sintassi.
per esempio la prima istruzione significa:
se sei nello stato 0, e leggi o 0 o 1, rimani nello stato 0, scrivi 0 (se hai letto 0) o scrivi 1 (se hai letto 1), e vai indietro.

la direzione viene indicata con > (destra), < (sinistra), - (rimani fermo)

il simbolo - è l'unico simbolo a cui bisogna stare attenti perche ha il significato di "niente" a seconda di dove viene usato, cioè per esempio:

0,a,0,-,>
cancella tutte le a presenti sul nastro, al posto di a ci mette "niente" (cioè spazio bianco).

0,-,1,*,>
se legge niente (cioè lo spazio bianco), scrive * al posto dello spazio bianco.

0,x,1,x,-
se legge x va nello stato 1, scrive x, e rimane fermo

[_Tipper]

Potresti dirmi anche il significato di init, rip, inc e code?

[Barnaba1]

semplicemente sono i nomi degli stati, invece di chiamarli 0 1, 2.. si chiamano per nome.

[_Tipper]

Ok, ti ringrazio Barnaba!