Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Valeria Vittorini » 4.La Macchina di Turing


Fondamenti di informatica

La macchina di Turing

Sommario

  • La Macchina di Turing
  • Calcolabilità e Algoritmo
  • Il Problema dell’Arresto

La Macchina di Turing

  • La Macchina di Turing (1936) è un modello fondamentale nella teoria dell’informatica.
  • Consente di approfondire il concetto di algoritmo.
  • Ha consentito di ottenere importanti risultati relativamente alla calcolabilità, alla complessità ed alla equivalenza di algoritmi.

Come è realizzata la TM

La Macchina di Turing è un ASF (vedi lezione 3) esteso con un meccanismo di lettura e memorizzazione dei simboli.

E’ di fatto un dispositivo composto da:

  • Un ideale nastro, cioè una striscia continua di celle ciascuna delle quali può essere vuota o contenere i simboli di un alfabeto.
  • Una testina di lettura-scrittura.
  • Un dispositivo di controllo (ASF) che in ogni istante si trova in uno tra un numero finito di stati.

Come opera la TM

La testina di lettura-scrittura può compiere le seguenti azioni elaborative (vedi lezione 2) elementari:

  • Spostamento testina di una posizione (a sinistra o a destra).
  • Scrittura di un simbolo nella cella sotto la testina (sostituendo il contenuto precedente).

Il dispositivo di controllo per ciascuna coppia (stato-simbolo letto):

  • Cambia stato
  • Esegue una delle azioni elaborative

Determinazione di una TM

Una TM è completamente individuata dalle seguenti informazioni:

  • Contenuto iniziale del nastro.
  • Descrizione della TM, d(TM):
    • Posizione iniziale della testina.
    • Stato iniziale del dispositivo di controllo.
    • Tabella delle transizioni di stato (che indica in corrispondenza della coppia stato-simbolo letto, oltre allo stato successivo ed all’eventuale simbolo scritto anche la direzione del movimento della testina).

TM e concetto di elaborazione

Una TM esegue una elaborazione Y=F(X) (vedi lezione 2)

  • X = nastro iniziale (t)
  • Y = nastro finale (t’)
  • F = d(TM): posizione iniziale, stato iniziale e tabella

NOTA: d(TM) descrive la macchina.

Esempio

  • Costruiamo una TM che risolva lo stesso problema affrontato nella lezione precedente (automi a stati finiti): costruiamo una macchina che valuti se il numero di occorrenze del simbolo 1 in una sequenza di 0 e 1 è pari.
  • In questo caso consideriamo in aggiunta che la sequenza debba iniziare e terminare con un simbolo speciale, ad esempio @.
  • Rappresentazione della sequenza: @0101110@
  • Rappresentazione del risultato:
    • Numero di 1 pari, la macchina scrive 1 nella prima casella a destra della stringa di ingresso
    • Numero di 1 dispari, la macchina scrive 0 nella prima casella a destra della stringa di ingresso

Modello di automa

Il dispositivo di Controllo è un automa:

Stati:

  • Stato S: stato iniziale in cui la macchina resta fino a quando non individua la stringa di ingresso sul nastro.
  • Stato P: il numero di 1 esaminato è pari.
  • Stato D: il numero di 1 esaminato è dispari.
  • Stato E: la macchina ha eseguito l’algoritmo e si ferma.

Ingressi

  • 1, 0, @

Uscite

  • Spostamento a destra (>), spostamento a sinistra (<), resta fermo (f), scrivi 1 (S1), scrivi 0 (S0)

Automa



Calcolabilità

  • Una TM che si arresti e trasformi un nastro t in un nastro t’ rappresenta l’algoritmo per l’elaborazione Y=F(X).
  • In altre parole la TM “calcola” Y=F(X).
  • Tesi di Church: non esiste un formalismo né una macchina concreta che possa calcolare una funzione F non calcolabile secondo Turing.

Definizione di algoritmo

  • Un algoritmo è ciò che può essere realizzato con una macchina di Turing!
  • Le funzioni sono tutte calcolabili? La risposta è NO! Cioè esiste una classe di funzioni F per le quali non esiste una macchina di Turing in grado di calcolarle.
    • In particolare, si dimostra che non esiste una TM – e quindi un algoritmo – in grado di decidere se data una qualsiasi macchina d(T) ed un qualsiasi nastro t, la macchina d(T) si arresta sul nastro t (problema dell’arresto).
  • Quindi: esistono problemi che per loro natura non sono risolvibili da alcuna macchina finora costruita!

Prossima lezione

  • Il concetto di Informazione
  • Elaborazione ed Algoritmo
  • Problema ed Istanza
  • Sequenza Statica e Sequenza Dinamica
  • Linguaggio e Programma

Indice letture

Materiali di studio

B. Fadini, C. Savy: Fondamenti di Informatica I, Liguori Editore: Parte1, Capitolo 1, par. 6, 7, 8, 9, 10, 11.

I materiali di supporto della lezione

B. Fadini, C. Savy: Fondamenti di Informatica I, Liguori Editore: Parte1, Capitolo 1, par. 6, 7, 8, 9, 10, 11

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion