Macchina di Turing: cos’è e come funziona


La Macchina di Turing è un modello teorico di un dispositivo di calcolo inventato dal matematico britannico Alan Turing negli anni ’30 del XX secolo. Questo modello è stato cruciale nello sviluppo della teoria dell’informazione e dei computer moderni. Nel suo saggio del 1948, “Intelligent Machinery“, Turing scrisse che la sua macchina era composta da:

una capacità di memoria illimitata ottenuta sotto forma di un nastro infinito delimitato in caselle, su ciascuna delle quali può essere stampato un simbolo. In ogni istante c’è un simbolo nella macchina, e viene detto simbolo scansionato. La macchina può alterare un simbolo scansionato in qualsiasi momenti, e il suo comportamento è determinato da quel simbolo e solo da quello scansionato. Il nastro può essere spostato avanti e indietro, essendo questa una delle operazioni elementari della macchina stessa. Qualsiasi simbolo sul nastro potrebbe eventualmente funzionare a turni.

Gli “ingredienti”

  • Nastro Infinito: Un’astrazione di un nastro infinito diviso in celle, ognuna contenente un simbolo da un alfabeto finito.
  • Testina di Lettura/Scrittura: Un dispositivo che può leggere il simbolo sulla cella attuale del nastro, sovrascrivere il simbolo o spostarsi a sinistra o destra sul nastro.
  • Stato: Un insieme finito di stati che rappresentano lo stato corrente della Macchina di Turing.
  • Transizioni: Una funzione che specifica come la Macchina di Turing cambia di stato e si muove sul nastro in base al simbolo letto dalla testina e allo stato corrente.
  • Programma: Una descrizione completa delle transizioni che definisce il comportamento della Macchina di Turing.

Descrizione formale della Macchina di Turing

Sia Q un insieme finito di stati, Σ un alfabeto finito (il set di simboli che possono essere scritti sul nastro), Γ un alfabeto finito che contiene Σ e un simbolo speciale “blank” che indica una cella vuota, e δ una funzione di transizione definita come segue:

δ: (Q – {qhalt}) × Γ → Q × Γ × {L, R}

dove:

  • Q è l’insieme di stati della macchina
  • qhalt è lo stato di arresto
  • Γ è l’insieme di simboli sul nastro
  • L e R indicano rispettivamente lo spostamento a sinistra e a destra della testina di lettura/scrittura.

La macchina di Turing opera seguendo questi passi:

  1. Inizia in uno stato iniziale q0 con il nastro contenente un input finito o infinito.
  2. Alla lettura di un simbolo a sulla cella attuale del nastro e trovandosi nello stato q, esegue la transizione (δ(q, a) = (q’, b, D)), dove:
    • q’ è il nuovo stato
    • b è il simbolo che sovrascrive a sulla cella
    • D è la direzione in cui la testina di lettura/scrittura si muove (L per sinistra, R per destra).
  3. Se q’ è qhalt, la macchina termina.
  4. Altrimenti, si sposta sullo stato q’ e ripete il processo.

Questo è il modello matematico di una Macchina di Turing, un concetto fondamentale nella teoria della computazione.

Versione video della spiegazione

A cosa serve la macchina di Turing

SI tratta del modello di computazione (o di calcolatore) più generale e potente che esista, ad un livello di astrazione tale che se un problema non si può risolvere con questa macchina, quasi certamente non si può risolvere in generale.

Esempio: alternare 0 e 1 sul nastro

Il primo esempio in assoluto di programma per computer dovrebbe risalire al 1936, anno in cui Turing pubblica il suo articolo On Computable Numbers, with an Application to the Entscheidungsproblem. Stampa semplicemente una sequenza di zero e di uno all’infinito, mettendo uno spazio tra un simbolo e l’altro.

L’animazione dovrebbe rendere l’idea, e restituisce anche il fatto che la macchina richieda un “codice”, ovvero una tabella con tutte le singole transizioni di stato, per poter funzionare.

via GIPHY

Esempio di Macchina di Turing: Somma di numeri binari

Supponiamo di avere una Macchina di Turing che deve sommare due numeri binari.

L’input sarà rappresentato sul nastro come sequenza di simboli 0 e 1, con uno spazio tra i due numeri.

La Macchina di Turing opera come segue:

  1. Legge il primo simbolo e va al primo numero.
  2. Somma i bit corrispondenti dei due numeri, tenendo conto di un eventuale riporto.
  3. Scrive il risultato sul nastro e va al bit successivo nei due numeri.
  4. Continua fino a quando entrambi i numeri sono stati esaminati.
  5. Se ci sono ulteriori bit nei numeri, li copia direttamente nel risultato.
  6. La Macchina di Turing si ferma quando entrambi i numeri sono completamente esaminati.

Ecco un diagramma di stato semplificato della Macchina di Turing:

Diagramma di stato della Macchina di Turing per l'addizione binaria

Questo esempio illustra un’applicazione pratica del concetto di Macchina di Turing nel calcolo di una somma binaria.

Macchina di Turing programmabile (emulatore)

https://turingmachine.io/

 

👇 Da non perdere 👇



Questo portale esiste da 4549 giorni (12 anni), e contiene ad oggi 4117 articoli (circa 3.293.600 parole in tutto) e 18 servizi online gratuiti. – Leggi un altro articolo a caso
Privacy e termini di servizio / Cookie - Il nostro network è composto da Lipercubo , Pagare.online e Trovalost
Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Questo sito contribuisce alla audience di sè stesso.