• 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

Turing, macchina di

Enciclopedia della Matematica (2013)
  • Condividi

Turing, macchina di


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 umano esegue un calcolo, la macchina di Turing è tuttora utilizzata, nelle sue numerose varianti, come modello astratto del calcolo automatico sviluppato da un elaboratore. Utilizzando questo modello, per esempio, si studiano, in relazione alla complessità di calcolo delle funzioni, le proprietà di determinismo o non determinismo dei singoli passi, della sequenzialità o del parallelismo delle operazioni.

Una macchina di Turing può essere interpretata fisicamente come l’interazione tra due “oggetti”: un dispositivo di controllo, che può trovarsi in un numero finito di stati, e una memoria esterna sequenziale, costituita da un nastro potenzialmente infinito diviso in celle in ciascuna delle quali è possibile leggere o scrivere un carattere dell’alfabeto della macchina. L’interazione è data da una testina di lettura/scrittura. In ogni istante, in base allo stato del controllo e al carattere letto, la macchina può:

a) cambiare o meno lo stato;

b) cambiare o meno il carattere sul nastro;

c) spostarsi o meno di una cella a sinistra o a destra.

figure

Il funzionamento della macchina può essere descritto da una funzione δ che a ogni coppia (stato, carattere letto) associa una terna (nuovo stato, nuovo carattere, mossa), dove il nuovo stato può anche essere lo stato stesso in cui la macchina si trova, così come il nuovo carattere può essere lo stesso carattere letto qualora questo non venga modificato; la mossa può essere uno spostamento a destra, uno spostamento a sinistra oppure nessuno spostamento. Indicati con Σ l’alfabeto dei caratteri con cui opera la macchina, con K l’insieme degli stati del suo dispositivo di controllo e con d, s, i le tre possibili mosse (traslazione di una cella a destra, di una cella a sinistra, traslazione identica cioè nessun movimento), la funzione δ che descrive il funzionamento della macchina di Turing è del tipo: K × Σ → K × Σ × {d, s, i }. L’alfabeto dei caratteri Σ = {σ0, σ1, …, σr} comprende un particolare carattere σ0, indicato come «spazio» o «blank» (espresso in letteratura anche con il simbolo □); l’insieme degli stati K = (q0, q1, …, qs} comprende due particolari stati, q0 e qƒ che sono, rispettivamente, lo stato iniziale e lo stato finale. Una macchina di Turing è, quindi, costituita da una sestupla {Σ, σ0, K, δ, q0, qƒ }. Una sua configurazione è una stringa del tipo σi 1σi 2… σinq j σin+1σin+2…σim, cioè un elemento dell’insieme Σ*KΣ+ dove Σ* indica l’insieme di tutte le stringhe costruite a partire dall’alfabeto Σ utilizzando i suoi caratteri, incluso il carattere vuoto, mentre Σ+ indica l’insieme di tutte le stringhe costruite con i caratteri di Σ escluso quello vuoto. Una configurazione è interpretabile come una triplice informazione:

• l’indicazione di una porzione finita di nastro σi 1σi 2…σinσin+1σin+2…σim contenente caratteri diversi dal blank, a differenza del resto del nastro che contiene solo il carattere blank;

• l’indicazione dello stato qj in cui si trova la macchina;

• l’indicazione del carattere σin+1, su cui è posizionata la testina della macchina.

Una configurazione si dice iniziale se qj = q0 mentre si dice finale se qj = qƒ.

Una transizione elementare di una macchina di Turing è una funzione C → C dove C è l’insieme delle sue possibili configurazioni e una transizione dalla configurazione c1, alla configurazione c2 è simbolicamente indicata con c1 ⊦ c2. Un calcolo di una macchina di Turing è una sequenza di configurazioni c1, c2, …, ck, … tale che c1 è una configurazione iniziale e per ogni i ≥ 1, ci ⊦ ci+1; se la sequenza c1, c2, …, ck è finita, allora ck deve essere una configurazione finale.

Una funzione aritmetica ƒ: Nn → N, che a una n-pla di numeri naturali associa un numero naturale, è calcolabile secondo Turing (o Turing-calcolabile o T-calcolabile) se esiste una macchina di Turing M tale che da una configurazione iniziale contenente una qualsiasi n-pla x1, …, xn produce una configurazione finale contenente y, essendo y = ƒ(x1, …, xn). Trattandosi di una macchina logica astratta, la formalizzazione dei numeri naturali da rappresentare è semplificata al massimo: il numero 0 è rappresentato con un simbolo, per esempio una barretta |, mentre il numero n è rappresentato da n + 1 barrette; l’alfabeto Σ della macchina può essere così ridotto a due soli simboli: {|, □}. L’insieme delle funzioni Turing-calcolabili coincide con l’insieme delle funzioni rappresentabili con altri formalismi costruiti per dare una definizione rigorosa al concetto di calcolabilità (→ Post, sistema di; → lambda-calcolo); tutti questi formalismi descrivono tutte e sole le funzioni ricorsive. La tesi di → Church afferma appunto che l’insieme delle funzioni ricorsive coincide con quello delle funzioni calcolabili.

Il funzionamento di una macchina di Turing è descritto dall’insieme di istruzioni relative al modo di operare della funzione δ: K × Σ → K × Σ × {d, s, i }; tali istruzioni sono anch’esse memorizzate sul nastro e danno alla macchina la possibilità di scorrere tra la zona dove esse sono memorizzate e la parte del nastro stesso dove essa opera. L’importanza di tale modello logico sta, quindi, proprio nel fatto che l’automa è in grado di memorizzare sia dati che istruzioni sullo stesso supporto e con le stesse caratteristiche, sebbene in locazioni diverse. Estendendo tale processo, Turing descrisse macchine che compiono azioni elementari (quali copiare un dato, cancellare un carattere ecc…) e macchine più complesse ottenute come composizione di macchine elementari e giunse a descrivere il funzionamento di un automa universale, detto appunto macchina universale di Turing, in grado di simulare ogni altra macchina di Turing. Tale automa universale è alla base delle successive evoluzioni che hanno portato agli automi a programma e all’organizzazione logica dei moderni computer.

Pur nella sua grande potenza logica, la macchina di Turing ha tuttavia un limite intrinseco: data una configurazione iniziale di una macchina di Turing non è decidibile a priori la sua possibilità di giungere a un termine, cioè a una configurazione finale (indecidibilità della fermata di una macchina di Turing). Come ogni automa, la macchina di Turing può essere utilizzata come riconoscitore di un linguaggio, stabilendo che una stringa scritta sul nastro di una macchina di Turing M appartiene al linguaggio L costruito a partire dall’alfabeto Σ di M se la macchina è in una configurazione finale quando giunge al termine della stringa. Come riconoscitore di linguaggi, una macchina di Turing è un automa molto generale, che ha come casi particolari altri automi, quale per esempio l’automa a stati finiti. Corrispondentemente, un linguaggio riconosciuto da una macchina di Turing ha caratteristiche più generali di quelli riconosciuti da automi più specifici; così è, per esempio, un linguaggio regolare che è riconosciuto da un automa a stati finiti (→ automa). Si costruisce così una gerarchia di linguaggi che corrisponde alla gerarchia di automi, il cui livello più alto è appunto la macchina di Turing: la sua generalità va tuttavia a scapito della decidibilità perché quanto più è generale un automa e ampia la classe dei linguaggi che esso può riconoscere, tanto più numerosi sono i problemi non decidibili che riguardano tali linguaggi.

Vedi anche
Alan Mathison Turing 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 di funzione effettivamente computabile ... 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 al loro significato ... 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’a. euclideo, delle divisioni successive, l’a. algebrico, insieme delle regole del calcolo ... calcolo Insieme di procedimenti matematici atti a dare la soluzione di un dato problema. Informatica Sistemi di c. Complesso di unità periferiche con le quali e per mezzo delle quali un calcolatore, specialmente di medie o grosse dimensioni, viene utilizzato per l’acquisizione, la restituzione, la conservazione ...
Tag
  • FUNZIONI CALCOLABILI
  • LINGUAGGIO REGOLARE
  • MACCHINA DI TURING
  • FUNZIONI RICORSIVE
  • LETTURA/SCRITTURA
Altri risultati per Turing, macchina di
  • macchina di Turing
    Enciclopedia della Scienza e della Tecnica (2008)
    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 ...
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