Macchina di Turing

Macchina di Turing

 

 

 

I riassunti , gli appunti i testi contenuti nel nostro sito sono messi a disposizione gratuitamente con finalità illustrative didattiche, scientifiche, a carattere sociale, civile e culturale a tutti i possibili interessati secondo il concetto del fair use e con l' obiettivo del rispetto della direttiva europea 2001/29/CE e dell' art. 70 della legge 633/1941 sul diritto d'autore

 

 

Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).

 

 

 

 

Macchina di Turing

 

La Macchina di Turing.

In sostanza il concetto di automa è quello di una macchina capace di svolgere in maniera automatica, una volta sollecitata in modo opportuno, delle operazioni particolari più o meno complesse che portano a un preciso risultato.
Per le loro caratteristiche, gli automi a stati finiti sono in grado di risolvere solo quella tipologia di problemi in cui il numero di eventi da ricordare risulta essere finito e determinato a priori.
Molti matematici si sono cimentati nella ricerca di macchine computazionali astratte in grado di risolvere qualsiasi tipo di problema, o per lo meno tutti quelli risolvibili attraverso un algoritmo. Si deve a A.M. Turing nel 1936 l’identificazione formale delle caratteristiche che una macchina astratta (modello matematico) deve avere per poter rappresentare un algoritmo. Si tratta di pura astrazione matematica, ma che rappresenta un potente strumento logico-concettuale che ha posto le basi degli studi che hanno condotto alla realizzazione dei calcolatori programmabili.
La macchina di Turing è un automa composto di tre elementi:

  • un nastro infinito, suddiviso in caselle, ciascuna delle quali può contenere un solo simbolo tra quelli appartenenti all’alfabeto finito d’ingresso/uscita o il carattere speciale blank;
  • una testina di lettura/scrittura, con la quale l’unità di controllo legge e scrive sul nastro un simbolo per volta; parallelamente alla testina c’è un meccanismo che muove il nastro a destra o a sinistra una sola casella alla volta;
  • un’unità di controllo a stati finiti.

Per simulare il funzionamento della macchina di Turing si:
1. definisce un alfabeto finito
2. sviluppano i vari stati attraverso la loro descrizione formale
3. risolve il problema mediante una tabella di transizione.
La macchina ha un funzionamento ciclico: legge un simbolo dal nastro, da esso e dallo stato interno in quell’istante determina un simbolo in uscita, un nuovo stato interno e un movimento sul nastro, fino a raggiungere uno stato senza configurazione successiva, stato finale del processo.
Ad ogni operazione di un algoritmo viene associata univocamente una terna di azioni che la macchina di Turing può svolgere. Pertanto si può ipotizzare che ad ogni algoritmo corrisponde un automa risolutore, rappresentato da un’appropriata macchina di Turing.
Ogni problema risolvibile tramite un algoritmo porta alla progettazione di una specifica macchina di Turing.
Da ciò l’associazione tra problema, algoritmo risolutore del problema, macchina di Turing che calcola l’algoritmo.
Successivamente alla macchina di Turing, evidentemente legata allo specifico problema, i matematici hanno introdotto la macchina di Turing universale, la cui logica di funzionamento non è più legata all’algoritmo in esecuzione. Si tratta di una macchina programmabile in grado di memorizzare la descrizione di una qualsiasi macchina di Turing e di simularne il comportamento, in pratica una macchina di Turing capace d’interpretare un’altra macchina di Turing. Facendo un parallelo tra teoria e realtà, la macchina di Turing è un calcolatore che svolge un solo programma, la macchina di Turing universale è un calcolatore con memorizzazione di più programmi, in grado di svolgere algoritmi diversi.

Fonte: http://www.maecla.it/Materiali_fortic/Percorso%20A/Mod%208%20A/Allegati%20mod8A/Approfondimento%202%20-%20Macchina%20Turing.doc

Sito web da visitare: http://www.maecla.it

Autore del testo: non indicato nel documento di origine

Il testo è di proprietà dei rispettivi autori che ringraziamo per l'opportunità che ci danno di far conoscere gratuitamente i loro testi per finalità illustrative e didattiche. Se siete gli autori del testo e siete interessati a richiedere la rimozione del testo o l'inserimento di altre informazioni inviateci un e-mail dopo le opportune verifiche soddisferemo la vostra richiesta nel più breve tempo possibile.

 

Macchina di Turing

 

 

I riassunti , gli appunti i testi contenuti nel nostro sito sono messi a disposizione gratuitamente con finalità illustrative didattiche, scientifiche, a carattere sociale, civile e culturale a tutti i possibili interessati secondo il concetto del fair use e con l' obiettivo del rispetto della direttiva europea 2001/29/CE e dell' art. 70 della legge 633/1941 sul diritto d'autore

Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).

 

Macchina di Turing

 

"Ciò che sappiamo è una goccia, ciò che ignoriamo un oceano!" Isaac Newton. Essendo impossibile tenere a mente l'enorme quantità di informazioni, l'importante è sapere dove ritrovare l'informazione quando questa serve. U. Eco

www.riassuntini.com dove ritrovare l'informazione quando questa serve

 

Argomenti

Termini d' uso, cookies e privacy

Contatti

Cerca nel sito

 

 

Macchina di Turing