Macchine di Turing deterministiche a nastro singolo
Una macchina di Turing deterministica (DTM, dall’inglese Deterministic Turing Machine) a nastro singolo è definita dalla tupla (Q, F, q0, Γ, δ), in cui:
- Q, F, q0, δ sono definiti esattamente come per i DFSA.
- Γ è l’alfabeto dei simboli del nastro.
Si possono definire DTM a K nastri. Tuttavia, ogni DTM a K nastri può essere trasformata in una DTM a nastro singolo. Per questo, ci focalizziamo su DTM a nastro singolo.
Notate che non nella definizione manca l’insieme dei simboli di ingresso I. Questo perché, nel caso di una DTM a nastro singolo, i simboli di ingresso sono scritti sul nastro, ed eventualmente sovrascritti.
La funzione di transizione
Per una DTM, la funzione di transizione è così definita:
δ: (Q - F) x Γ → Q x Γ x <R, L, S>
Ovvero: considerato lo stato attuale e il simbolo attualmente puntato sul nastro, la funzione di transizione indica qual è il nuovo stato da raggiungere, quale simbolo scrivere nella cella del nastro, quale movimento eseguire sul nastro:
- R - Right - sta per: “spostamento a destra di una cella”
- L - Left - sta per: “spostamento a sinistra di una cella”
- S - Stay - sta per: “rimani sulla cella del nastro attuale”
Per indicare la volontà di leggere una cella vuota dal nastro, si utilizza il simbolo _.
Nota bene: le DTM accettano/riconoscono una sequenza quando, semplicemente, raggiungono uno stato finale. Diversamente da DFSA e DPDA, non è richiesta la lettura completa della sequenza di input!
La transizione
Ecco un esempio di transizione in una DTM:
La transizione qui sopra indica che, se l’automa è nello stato A e la testina è posizionata su una cella del nastro contenente il simbolo a,
allora bisogna passare allo stato B e scrivere nella cella puntata dalla testina il simbolo X. Infine, la testina deve spostarsi di una cella a destra (
Il diagramma degli stati
Un’automa può essere efficacemente rappresentato attraverso un diagramma degli stati. Ecco un esempio di diagramma degli stati per una DTM:
Lo stato iniziale è indicato attraverso una freccia che parte dal nulla e raggiunge tale stato.
Gli stati finali sono contraddistinti da una doppia circolettatura.
La tabella di transizione
Una funzione di transizione può essere efficacemente rappresentata attraverso una tabella di transizione.
Ecco un esempio di tabella di transizione, riferita all’automa dell’esempio precedente:
TODO