{"id":3387,"date":"2013-04-10T00:00:00","date_gmt":"2013-04-09T22:00:00","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"3387","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/3387\/","title":{"rendered":"Potreste farmi un esempio di macchina di Turing che calcola la somma di due numeri? (esempio che faccia 1+1=2)?"},"content":{"rendered":"

Una macchina di Turing<\/a> è un modello concettuale di calcolatore. La sua utilità è legata prevalentemente alla teoria della computabilità, infatti attraverso operazioni semplicissime la macchina di Turing sarebbe in grado di poter eseguire ogni possibile algoritmo (tesi di Church-Turing<\/a>).<\/p>\n

Il modello è costituito da un nastro indefinito che può essere letto e scritto, dato un insieme di simboli (senza perdere di generalità possono essere 0 e 1), da una testina che si muove a destra e a sinistra. Il sistema può assumere un predefinito numero di stati, tra cui lo stato finale che indica che l’algoritmo si è concluso in modo corretto.<\/p>\n

Il comportamento della macchina è definito attraverso una tabella di istruzioni: per ogni stato e per ogni simbolo letto sono definite le azioni, cioè l’eventuale scrittura, l’eventuale cambio di stato e lo spostamento a destra o a sinistra. Fa parte integrante del modello l’interpretazione dei dati di ingresso e di uscita.<\/p>\n

Il caso della somma di due numeri è trattato ad esempio qui<\/a>.<\/p>\n

Supponendo di trattare numeri interi positivi rappresentati dalla sequenza di 1 di lunghezza pari al numero da memorizzare, e supponendo che i due numeri da sommare siano separati da uno zero, la tabella delle istruzioni necessarie per produrre il numero somma è molto semplice ed è riportata qui sotto.<\/p>\n

\"\"<\/p>\n

A parole: partendo dall’inizio del nastro bisogna scorrere a destra (S1) fino a trovare un 1; cancellare il primo 1 e scorrere a destra fino a trovare uno 0 (S2); quindi basta riempire lo 0 tra i due numeri con un 1 (END). Ora è memorizzato il numero somma dei due numeri iniziali.<\/p>\n

Qui sotto vengono rappresentate le configurazioni del nastro ad ogni passo per il caso della somma 4 + 2.<\/p>\n

\"\"<\/p>\n

Il fatto che le istruzioni siano così elementari in alcuni casi complica un po’ gli algoritmi: si pensi ad esempio di dover copiare un numero, sempre memorizzato come sequenza di 1, e scriverlo di seguito al primo numero, separato da uno 0. Per contare gli 1 semplicemente incrementando una variabile (stato) è necessario porre un limite superiore ai numeri da rappresentare.<\/p>\n

Per copiare numeri di qualunque lunghezza bisogna copiare una cifra per volta attraverso un ciclo che riporta lo stato ad un valore precedente. La tabella delle istruzioni è descritta qui<\/a>.<\/p>\n

Si vedano anche i seguenti link:<\/p>\n

http:\/\/en.wikipedia.org\/wiki\/Turing_machine_examples<\/a><\/p>\n

http:\/\/www.digitanto.it\/pages\/Multiframe.htm?f=http:\/\/www.digitanto.it\/Articoli\/AppuntiDiInformatica14.htm<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

[…]<\/p>\n","protected":false},"author":155,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62],"tags":[],"class_list":["post-3387","post","type-post","status-publish","format-standard","hentry","category-software"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/3387","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/155"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=3387"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/3387\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=3387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=3387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=3387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}