La macchina di Turing in breve
Cos’è una macchina di Turing
Una macchina di Turing è un modello teorico di calcolo che serve a rispondere a una domanda fondamentale:
Che cosa significa, in modo preciso, “calcolare” qualcosa?
Non è una macchina reale: è un oggetto matematico ideale, estremamente semplice, ma sorprendentemente potente.
Il suo scopo non è essere veloce o pratica, ma catturare l’essenza del calcolo algoritmico.
L’idea chiave è questa:
Una macchina di Turing esegue un calcolo seguendo regole meccaniche, finite e precise, passo dopo passo, senza “capire” quello che fa.
Funzionamento
Immagina:
- un nastro infinito diviso in caselle
- una testina che può leggere e scrivere su una casella alla volta
- un insieme finito di stati interni (come “modalità mentali” della macchina)
- un insieme di regole che dicono cosa fare in ogni situazione
La macchina lavora così:
- guarda il simbolo sotto la testina
- guarda lo stato in cui si trova
- applica una regola che dice:
- cosa scrivere
- come muovere la testina
- in quale nuovo stato andare
Poi ripete.
Il nastro
- È una sequenza infinita di celle
- Ogni cella contiene un simbolo
- All’inizio contiene l’input, il resto è vuoto
Intuitivamente:
il nastro è memoria + input + output, tutto insieme
I simboli
C’è un insieme finito di simboli, ad esempio:
0,1- un simbolo speciale di vuoto (di solito
□)
I simboli sono gli unici “oggetti” che la macchina può vedere e manipolare.
La testina
La testina:
- legge un solo simbolo alla volta
- può scrivere un simbolo
- può muoversi:
- a sinistra (L)
- a destra (R)
- (talvolta restare ferma)
Gli stati
Gli stati rappresentano:
la memoria finita di controllo della macchina
Non memorizzano dati complessi, ma indicano:
- “in che fase dell’algoritmo sono”
- “cosa sto cercando di fare adesso”
Esempi intuitivi:
- stato “sto cercando l’inizio”
- stato “sto copiando”
- stato “ho finito”
gli stati sono finiti e non crescono mai → tutta la memoria “grande” sta nel nastro.
La funzione di transizione
È il programma della macchina.
Dice:
Se sono nello stato X e leggo il simbolo Y, allora:
- scrivi Z
- muovi la testina
- vai nello stato W
È una tabella di istruzioni completamente deterministica (in una TM classica).
Arresto
La macchina termina quando:
- entra in uno stato finale
- oppure quando non esiste alcuna regola applicabile
In breve…
Una macchina di Turing è:
- memoria infinita ma stupida (nastro)
- controllo finito ma preciso (stati)
- comportamento totalmente meccanico (regole)
Ed è sorprendente perché:
qualsiasi algoritmo eseguibile da un computer può essere simulato da una macchina di Turing
Formalizzazione matematica
Ruolo chiave degli stati Q
- gli stati sono la logica
- il nastro è la memoria
- la macchina “pensa” solo cambiando stato
- tutto il calcolo emerge dall’interazione tra:
- stato finito
- memoria infinita
- regole locali
