Scusa, ma la mdt non la programmate piu' con la tabella degli stati?
La mitica tabella <stati>*<simboli> contenente la tripla (nuovo stato, simbolo da scrivere, direzione movimento testina)?
?
Comunque, la mdt e' un automa a stati. puoi iniziare a costruire l'automa, poi lo converti.
Certo, devi anche immaginare l'algoritmo da utilizzare.
Ma come dice la tesi di Church:
ogni funzione intuitivamente computabile, e' computabile