Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
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