• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

macchina di Turing

di Mauro Cappelli - Enciclopedia della Scienza e della Tecnica (2008)
  • Condividi

Macchina di Turing

Mauro Cappelli

Modello di agente di calcolo adatto a simulare la logica di qualsiasi algoritmo computazionale. La macchina formale fu proposta nel 1936 dal logico e matematico britannico Alan Turing, come sistema astratto che, opportunamente programmato, era capace di eseguire ogni tipo di operazione (l’idea di Turing era di rendere automatica una macchina da scrivere). Oggi ne esistono molte varianti, la più semplice delle quali è la macchina di Turing a nastro, formata da un’unità di controllo contenente un programma con un numero finito di istruzioni, da un nastro di lunghezza illimitata suddiviso in celle e da un’unità di lettura e scrittura sul nastro in grado di spostarsi avanti e indietro di un numero qualsiasi di celle e di leggere e scrivere in una qualsiasi delle celle un simbolo di un alfabeto prefissato. Questa macchina, pur nella sua semplicità, può calcolare in un numero finito di passi elementari qualsiasi funzione computabile. Il nastro si estende idealmente in modo infinito nei due versi e risulta diviso in celle, ciascuna contenente un simbolo appartenente a un insieme finito di simboli detto alfabeto.

Ogni ;macchina di Turing deve possedere un alfabeto che contenga il simbolo speciale b (blank, spazio), i simboli 0 e 1, e un numero finito di altri simboli, come X e Y, usati come segnaposto. In ogni istante solo un numero finito di celle contiene simboli diversi da b. Il nastro funziona pertanto da input, da output e da memoria. La macchina è costituita da un numero finito k di stati o configurazioni ed è pensata per eseguire solo un tipo di operazione primitiva. A ogni operazione corrispondono tre azioni o comandi: scrittura di un nuovo simbolo nella cella, posizionamento in un nuovo stato, spostamento di una cella verso destra o verso sinistra. Le istruzioni possibili per la macchina sono: stato corrente, simbolo corrente, prossimo simbolo, prossimo stato, direzione di spostamento. Una macchina di Turing può eseguire un’intera sequenza di istruzioni, poiché risulta sincronizzata da una sorta di orologio interno. La macchina è pertanto un modello di agente di calcolo generale che modellizza ciò che effettivamente può compiere un calcolatore.

La macchina di Turing ha permesso di dimostrare che alcuni problemi non ammettono nessuna soluzione generale calcolabile. La tesi o congettura di Church-Turing afferma infatti che, se esiste un algoritmo per eseguire un compito che manipola simboli, allora esiste una macchina di Turing in grado di eseguire quel compito. Pertanto, è possibile utilizzare il modello della macchina di Turing per definire i limiti della computabilità: se per un problema non esiste una macchina di Turing in grado di risolverlo allora il problema si dice incomputabile o irrisolvibile.

→ Complessità algoritmica; Informatica teorica; Intelligenza artificiale; Sistemi chimico-fisici: autorganizzazione

Vedi anche
Alan Mathison Turing Turing ‹ti̯ùriṅ›, Alan Mathison. - Matematico e logico matematico britannico (Londra 1912 - Manchester 1954). Pioniere della scienza dell'informazione e dell'intelligenza artificiale, ha legato il suo nome, in particolare, a un metodo da lui indicato per dare un significato preciso al concetto intuitivo ... algoritmo matematica Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo (per es. l’algoritmo euclideo, delle divisioni successive, l’algoritmo algebrico, insieme delle regole ... rete neurale In informatica, tipo di calcolatore costituito da un numero elevato di processori elementari, collegati fra loro da una estesa rete di interconnessioni, in modo da realizzare architetture a elevato grado di parallelismo. ● A differenza dei calcolatori tradizionali, che contengono generalmente una sola ... lògica matemàtica lògica matemàtica Branca della logica, che utilizza un linguaggio simbolico e adotta un sistema di calcolo di tipo algebrico per esaminare le espressioni di un discorso deduttivo. Queste ultime possono essere considerate formalmente come oggetti grafici combinabili tra loro (sintassi) o in relazione ...
Categorie
  • LOGICA in Filosofia
  • ELABORATORI in Informatica
Tag
  • INTELLIGENZA ARTIFICIALE
  • INFORMATICA TEORICA
  • ALAN TURING
  • ALGORITMO
Altri risultati per macchina di Turing
  • Turing, macchina di
    Enciclopedia della Matematica (2013)
    Turing, macchina di automa universale, elaborato dal logico inglese A.M. Turing, che fornisce una traduzione formale del concetto intuitivo di → calcolabilità. Sebbene introdotta da Turing nella prima metà del secolo scorso (1937) come modello per analizzare i successivi passi secondo cui un essere ...
Vocabolario
màcchina
macchina màcchina (ant. màchina) s. f. [dal lat. machĭna, che è dal gr. dorico μαχανά, attico μηχανή]. – 1. In senso storico e antropologico, qualsiasi dispositivo o apparecchio costruito collegando opportunamente due o più elementi in...
macchina del fango
macchina del fango loc. s.le f. (spreg.) Insieme di notizie calunniose orchestrate con l’obiettivo di rovinare la reputazione di qualcuno. ◆ [tit.] La macchina del fango. (Repubblica, 27 ottobre 2009, Prima pagina) • Se non si muove, se...
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali