Appunti esame elementi di teoria della computazione

Descrizione informale di una MdT

Una macchina di Turing utilizza un nastro semi-infinito. Inizialmente il nastro contiene solo la stringa di

input. La macchina di Turing ha una testina di lettura e scrittura, che può muoversi lungo il nastro. In

funzione dello stato in cui si trova e del simbolo input letto, la macchina cambia stato, scrive un simbolo

nella cella su cui era posizionata, sposta la testina di una posizione a destra o a sinistra. La macchina

continua a computare finché non accetta o rifiuta. Se non raggiunge uno stato corrispondente a uno delle

due situazioni precedenti, la computazione andrà avanti per sempre.

Differenze tra una MdT e un automa a stati finiti

La definizione di Macchina di Turing (in seguito abbreviata con MdT o con TM) che daremo, metterà in

evidenza le seguenti differenze con il modello automa finito:

• Una MdT ha un nastro semi-infinito (infinito a destra), diviso in celle, ciascuna contenente un

carattere.

• Una MdT ha una testina che può muoversi a sinistra o a destra (ma non può oltrepassare il limite a

sinistra del nastro).

• la testina può leggere o scrivere caratteri (testina di lettura-scrittura).

•

Una MdT ha due stati speciali , rispettivamente corrispondenti all’accettazione e al

rifiuto della stringa input. Se la MdT si trova in uno di tali stati non può effettuare ulteriori passi di

computazione. (La frase sul testo di Sipser è: Gli stati speciali di accettazione e rifiuto hanno effetto

immediato. Ossia la macchina si ferma immediatamente quando raggiunge uno dei due stati)

• Non c’è limite ai passi di computazione (in particolare il numero di tali passi non è limitato dalla

lunghezza dell’input).

Esempio di Macchina di Turing

|

{0

= 1 > 0}

Una macchina di Turing che accetta

(Descrizione ad alto livello)

(passo 1) Se legge 0 lo sostituisce con X, se legge 1 rifiuta, se legge Y va al passo 4.

(passo 2) Scorre il nastro verso destra, se trova 1 lo sostituisce con Y , altrimenti rifiuta.

(passo 3) Scorre il nastro a sinistra fino a incontrare X, si sposta a destra e ripete dal passo 1.

(passo 4) Scorre il nastro a destra. Se legge solo delle Y e poi il simbolo di cella vuota, accetta. Altrimenti

rifiuta. 000111→X00111…→X00Y11…→XX0Y11…→XXXYYY

Definizione formale di una MdT

Definizione

Una Macchina di Turing deterministica è una settupla

(, )

= Σ, Γ, , , ,

0

dove:

• Q: Insieme finito degli stati (⊔∉ )

• Σ: Alfabeto dei simboli input ∈ , ⊂ , , ∉ )

• Γ: Alfabeto (finito) dei simboli di nastro (⊔

(

∶ \{; } ) × → × × {, }

• funzione di transizione

∈

• : stato iniziale

0

∈ :

• stato di accettazione

∈ : ≠

• stato di rifiuto,

NOTA: Spesso (nel libro, sui lucidi) l’aggettivo deterministica è sottinteso.

NOTA: Q, Σ e Γ sono insiemi finiti.

• Σ è un sottoinsieme di Γ.

• ⊔ ∈ ⊔∉

Σ è un sottoinsieme proprio di Γ perché .

• Q non è mai vuoto.

• ⊔.

Γ può contenere altri simboli oltre a quelli di Σ e a

NOTA: Esistono molte varianti di questa definizione che hanno lo stesso potere computazionale (o

espressivo), cioè riconoscono la stessa classe di linguaggi.

Vedremo due varianti: la macchina di Turing multi-nastro e la macchina di Turing non deterministica.

Funzione di transizione di una MdT

(, )una

= Σ, Γ, , , ,

Sia MdT deterministica.

0

Il suo comportamento è descritto dalla funzione di transizione

( })

{, {,

∶ \ × → × × }

′ ′ ′ ′

(, ) ( ) {,

= , , , ∈ , , ∈ , ∈ }

Se , sappiamo che

′ ′

(, ) ( )

= , ,

Se e se M si trova nello stato q con la testina posizionata su una cella contenente γ,

alla fine della transizione:

• M si troverà nello stato q’,

′ ∈

• sarà il simbolo scritto sulla cella del nastro su cui la testina si trovava ALL’INIZIO della

transizione (contenente γ),

• la testina si sarà spostata sulla cella di sinistra se (tale cella esiste e se) d = L, sulla cella di destra se

d = R. ′ ′

(, ) ( )

= , ,

NOTA: Data , se M si trova nello stato q con la testina posizionata su una cella

contenente γ e se tale cella è quella più a sinistra del nastro, la testina non si sposta e resta sulla cella del

nastro su cui si trovava all’inizio della transizione.

Spesso nel progetto di una Macchina di Turing si definisce una transizione che scrive un carattere speciale

nella cella più a sinistra del nastro e che serve a individuarla.

Diagramma di stato di una MdT

Come nel caso degli automi, spesso preferiamo utilizzare il diagramma di stato di una specifica Macchina di

Turing piuttosto che la descrizione formale della settupla.

Il diagramma di stato di una Macchina di Turing è un grafo i cui nodi hanno come nomi gli stati della

macchina.

Le etichette degli archi hanno la forma: “ → , "

{,

∈ }.

dove “simbolo” è un simbolo di Γ e d Il simbolo a sinistra della freccia rappresenta il simbolo letto,

quello dopo la freccia il simbolo (eventualmente lo stesso) che sostituisce il simbolo letto per effetto della

transizione, d lo spostamento per effetto della transizione.

Ad esempio, se sull’arco dal nodo al nodo compare l’etichetta:

1 2 0 → ⊔,

questo corrisponde a: ( 0) ( )

, = ,⊔,

1 2

Alle volte si usa l’abbreviazione di non indicare il carattere dopo la freccia se esso non è modificato dalla

transizione.

Ad esempio, se sull’arco dal nodo al nodo troviamo l’etichetta:

3 4 0→

( 0) ( )

, = , 0,

questo vuol dire che .

3 4

Computazione di una MdT - descrizione informale

Una MdT M inizia la computazione:

• partendo dallo stato iniziale ,

0

∗

∈ Σ

• con l’input posizionato sulla parte più a sinistra del nastro: le prime n celle a sinistra,

⊔),

se n =|w| è la lunghezza dell’input (il resto delle celle conterrà il carattere con la testina

posizionata sulla cella contenente il primo simbolo di input (quello più a sinistra)

⊔,

• Poiché Σ non contiene il carattere all’inizio della computazione il primo simbolo blank sul nastro

individua la fine dell’input.

• La computazione di M procede secondo le regole descritte dalla funzione di transizione.

• La computazione di M procede fino a quando non viene raggiunto uno stato di accettazione o

rifiuto. Se nessuno dei due stati viene raggiunto, M va avanti per sempre.

La computazione termina se M raggiunge

• lo stato di accettazione : Accetta input

• lo stato di rifiuto : Rifiuta input

NOTA: La computazione può non terminare. (Analogia: while C do Something dove C è una condizione

sempre vera).

Esempio

:

(, ),

= Σ, Γ, , , , { , , },

con Q = Σ = {a, b}, Γ = {a, b,⊔},

0 0

δ(q0, a) = (q0, a, R),

δ(q0, b) = (q0, b, L),

⊔)

δ(q0, = (qaccept,⊔, L).

NOTA: ”M non accetta l’input w” non è equivalente a “M rifiuta l’input w”. M può accettare un input w o

non accettare w. Se non accetta w, questo vuol dire che:

1. M rifiuta w

2. La computazione di M su w non termina.

È possibile simulare un automa finito deterministico attraverso una MdT.

La computazione di un automa finito deterministico su un input w può essere rappresentata da una

sequenza di stati (gli stati che rappresentano i nodi del cammino di etichetta w nel diagramma di stato che

rappresenta l’automa).

La posizione della testina è implicitamente rappresentata nella computazione poiché a ogni transizione si

sposta di una cella a destra.

Il nastro è di sola lettura, il contenuto del nastro non viene modificato durante la computazione e quindi

non è necessario considerarlo.

Computazione di una MdT – descrizione formale.

Configurazioni

Nella computazione di una macchina di Turing su un input w abbiamo bisogno di considerare tutti questi

elementi:

• stato

• posizione della testina ⊔ ⊔).

• la parte iniziale del nastro contenente tutti i caratteri diversi da (eventualmente separati da

Nota: è sempre costituita da un numero finito di celle.

Un’impostazione di questi tre elementi è chiamata una configurazione della macchina di Turing.

Intuitivamente una configurazione di una MdT è l’insieme delle informazioni costituito da una porzione

“abbastanza lunga” del nastro, dalla posizione della testina e dallo stato della MdT a un dato istante.

Definizione

Una configurazione C di una MdT ∗ ∗

(, )

= Σ, Γ, , , , = ∈

è una stringa: , dove:

0

∈

• è lo stato corrente di M,

∗

∈ Γ ⊔

• è il contenuto del nastro (con la convenzione di aver eliminato tutti i simboli dopo v, cioè

dopo l’ultimo carattere di v il nastro contiene solo simboli blank),

• la testina è posizionata sul primo simbolo di v.

Ad esempio: 1011 01111

7

rappresenta la configurazione in cui il nastro contiene

101101111⊔…⊔…

dove lo stato corrente è e la testina è posizionata sul secondo 0.

7

Nota: se C = uqv è una configurazione di una macchina di Turing, allora :

• u è la stringa di caratteri a sinistra del simbolo su cui è posizionata la testina.

• Sia u che v possono essere uguali a

Configurazioni: casi particolari

Se C = qv è una configurazione di una MdT allora la testina è posizionata sulla prima cella del nastro

(posizione della testina a inizio nastro).

Se C = uq è una configurazione di una MdT allora la testina è posizionata sulla prima cella della porzione del

⊔ ⊔).

nastro contenente solo (posizione della testina sulla porzione del nastro contenente solo

Passo di computazione

Intuitivamente un passo di computazione è la trasformazione della configurazione C1 nella configurazione

C2 per effetto di una applicazione della funzione di transizione. È una relazione tra coppie di configurazioni

definita dalla funzione di transizione.

Sia (, )

= Σ, Γ, , , , una MdT deterministica.

0 ∗

, ∈ , , , ∈ Γ , ∈ Γ .

Siano

Diremo che: ( ) (

, = , , ).

se

Diremo che ( ) (

, = , , ).

se

Nota: ua bv, u acv, uac v sono configurazioni di M.

La definizione generale è più complessa perché bisogna considerare anche i casi particolari (C = qv, C = uq

).

con u, v eventualmente uguali a

Ad esempio: ( ) (

, = , , ).

se

( ) (

, = , , ).

se

≠ .

Occorre distinguere u = da u

Siano due configurazioni di una MdT M.

Se C1 produce C2, scriveremo: 1 → 2

→

Il simbolo ,rappresenta la trasformazione di C1 in C2 e prende il nome di passo di computazione.

→ corrisponde a un’applicazione della funzione di transizione di M.

Definizione

Una configurazione C si dice: ∗

= , ∈ Σ

• iniziale (con input w) se con ,

0 ∗ ′

, ∈ Γ ∈ { , }

• di arresto se C = uqv, con e (non esiste nessuna configurazione

′

→

tale che ), ∗

, ∈ Γ =

• di accettazione se C = uqv, con e ,

∗

, ∈ Γ =

• di rifiuto se C = uqv, con e .

Nota: Le configurazioni di arresto sono configurazioni di accettazione o di rifiuto.

Definizione

Siano C, C’ configurazioni.

∗ ′

→ , … , > 1

se esistono configurazioni tali che:

1

=

• 1 {1,

→ ∈ … , − 1}

• (ogni produce )

+1, +1

′

=

• .

∗ ′

→

Diremo che è una computazione (di lunghezza k − 1).

Sia M una MdT e sia C una configurazione di M. Ci sono tre possibili casi:

∗ ′

→

1. con C’= u v configurazione di accettazione (M si ferma in ).

∗ ′

→

2. con C’= u v configurazione di rifiuto (M si ferma in ).).

∗ ′ ∗ ′ ′′

→ → →

3. Per ogni configurazione C’ tale che esiste una configurazione C’’ tale che

(M non si arresta).

Parola accettata da una MdT

Definizione ∗ ∗ ′

∈ Σ →

Una MdT M accetta una parola se esiste una computazione , dove C = è la

0

′

=

configurazione iniziale di M con input w e è una configurazione di accettazione.

∗

∈ Σ , , … , , > 1

Quindi M accetta se e solo se esistono configurazioni tali che:

1 2

=

• è la configurazione iniziale di M con input w

1 0 {1,

→ ∈ … , − 1}

• +1,

• è una configurazione di accettazione.

∗ ∗ ′

∈ Σ →

Allo stesso modo, M rifiuta una parola se esiste una computazione , dove C = è la

0

′

=

configurazione iniziale di M con input w e è una configurazione di rifiuto.

∗

∈ Σ

Quindi M si ferma su se M accetta w oppure rifiuta w, cioè se e solo se esistono configurazioni

, , … , , > 1 tali che:

1 2

=

• è la configurazione iniziale di M con input w

1 0 {1,

→ ∈ … , − 1}

• +1,

• è una configurazione di arresto.

∗

∈ Σ

Dunque, data una MdT M e una stringa , ci sono solo due possibili casi:

• M accetta w

• M non accetta w in quanto :

o M rifiuta w

o La computazione di M non si arresta mai sull’input w

Domanda: … ∈ Σ.

Sia M una MdT. Sia w = Supponiamo che w è accettata da M.

1

∗

, ∈ Γ

Quindi esistono tali che: ∗

→

0

Possiamo concludere che in questa computazione M deve aver letto tutti i caratteri di w?

E quindi che la computazione deve avere lunghezza almeno n = |w|?

Risposta

: ciò non è necessario, in quanto la condizione da verificare può essere vera prima di aver letto

tutti i caratteri della stringa w. Ad esempio, se la MdT accetta stringhe che iniziano per a, mi basta leggere

solo il primo carattere presente sul nastro , ignorando tutti i restanti.

Linguaggio riconosciuto da una MdT

Definizione

(, )

= Σ, Γ, , , ,

Sia una MdT. Il linguaggio L(M) riconosciuto da M, è l’insieme delle

0

stringhe che M accetta: ∗ ∗ ∗

() |

{

= ∈ Σ ∃, ∈ Γ → }

0

Quind