Dimostrazione TCC sulle Macchine di Turing
43 views
Skip to first unread message
Gianluca Di Vincenzo
Sep 2, 2014, 3:39:24 AM9/2/14
to informa...@googlegroups.com
Salve a tutti e grazie in anticipo per le vostre risposte :-)
La dimostrazione per il quale chiedo il vostro cortese aiuto è situata al terzo foglio dei compiti del 23 Novembre 2010 ed è la seguente:
“Dimostrare che è possibile trovare una TM che sottrae 1 a un intero > di 1 scritto in binario.”
Grazie a tutti per il cortese aiuto.
overload
Sep 3, 2014, 10:29:47 AM9/3/14
to informa...@googlegroups.com
Una maniera di dimostrare che questa TM esiste e' quella di
specificarne una e poi dire "toh, esiste ed e' questa qua".
Non ho intenzione adesso di fare tutta la formalizzazione dei sistemi di transizione ecc., ma l'idea e' quella di andare per "case analysis".
Esempio, il caso "numero che finisce per 1" e' facile:
e.g., 111111 -> 111110 (cioe', cancello l'uno tutto a dx e metto uno zero) [la freccia sta per transizione].
Poi c'e' il caso se il numero finisce con zero, ed allora li e' tipo
110 -> 101
1100 -> 1011
11000 -> 10111
100 -> blank 11
e via discorrendo. Quindi, la regola dovrebbe essere una roba del tipo "scorri verso sx finche' non incontri un uno, sostituiscilo con zero [o blank, se ...] e poi ritorna a destra e butta uno a pioggia".
Comunque, ho dato solo l'idea di come deve essere risolto. I dettagli, cioe' come formalizzare l'abbozzo di idea che ho scritto, li lascio a te. Ovviamente, considera tutta la menata riguardante i simboli di blank etc., perche' sono importanti per capire dove inizia e dove finisce il numero.
Ad ogni modo, sul libro dovrebbe esserci l'esempio del +1, se ricordo bene (ma forse ricordo male). Se c'e', rifatti a quello.
Non ho intenzione adesso di fare tutta la formalizzazione dei sistemi di transizione ecc., ma l'idea e' quella di andare per "case analysis".
Esempio, il caso "numero che finisce per 1" e' facile:
e.g., 111111 -> 111110 (cioe', cancello l'uno tutto a dx e metto uno zero) [la freccia sta per transizione].
Poi c'e' il caso se il numero finisce con zero, ed allora li e' tipo
110 -> 101
1100 -> 1011
11000 -> 10111
100 -> blank 11
e via discorrendo. Quindi, la regola dovrebbe essere una roba del tipo "scorri verso sx finche' non incontri un uno, sostituiscilo con zero [o blank, se ...] e poi ritorna a destra e butta uno a pioggia".
Comunque, ho dato solo l'idea di come deve essere risolto. I dettagli, cioe' come formalizzare l'abbozzo di idea che ho scritto, li lascio a te. Ovviamente, considera tutta la menata riguardante i simboli di blank etc., perche' sono importanti per capire dove inizia e dove finisce il numero.
Ad ogni modo, sul libro dovrebbe esserci l'esempio del +1, se ricordo bene (ma forse ricordo male). Se c'e', rifatti a quello.
--
Hai ricevuto questo messaggio perché sei iscritto al gruppo "informatica-aq" di Google Gruppi.
Per annullare l'iscrizione a questo gruppo e non ricevere più le sue email, invia un'email a informatica-a...@googlegroups.com.
Per postare in questo gruppo, invia un'email a informa...@googlegroups.com.
Visita questo gruppo all'indirizzo http://groups.google.com/group/informatica-aq.
Per altre opzioni visita https://groups.google.com/d/optout.
Gianluca Di Vincenzo
Sep 5, 2014, 4:36:48 AM9/5/14
to informa...@googlegroups.com
Grazie mille utilissimo, cercherò di arrivare da solo alla tua intuizione. Spero possa servire anche ad altri grazie ancora :-)
Reply all
Reply to author
Forward
0 new messages