Corso di Automi e Linguaggi Formali

Corso di Automi e Linguaggi Formali

Sommario della seconda parte

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.1/13

Macchine di Turing

Tesi di Church

Definizione di MdT: stati, alfabeto, stato iniziale, stati di alt, funzione di transizione Configurazione: stato, simbolo sotto la

testina, stringa a sinistra della testina, stringa a destra

M calcola f: si ferma per
^{  }



, va in loop altrimenti

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.2/13

Turing calcolabilita’



parzialmente Turing-calcolabile: se c’e’ una MdT che la calcola



Turing-calcolabile: se parz.

Turing-calcolabile e ^{ }

 

semi-decidibile: MdT che da’ 1 se
^ e altrimenti non si ferma

decidibile: se MdT che decide (si ferma) per ogni stringa se e’ in L o no

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.3/13

Estensioni di MdT

Piu’ nastri, una testina per nastro Piu’ testine e un solo nastro

Nastri multi-dimensioni Nastri ad accesso casuale Nondeterminismo

... Tutte simulabili da una MdT standard (piu’

lenta)

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.4/13

Linguaggi Turing enumerabili

decidibile

decidibile Semidecidibile = enumerabile

semidecidibile se: ^{ }



per^ parzialmente Turing calcolabile

Oppure: se ^{ }



per^ parzialmeente Tuting-calcolabile

decidibile enumerabile (semi-dec.)

e

enumerabili decidibile

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.5/13

Indecidibilita’

MdT universale: simula ogni altra MdT su ogni input

Codifica di una MdT Enumerazione delle MdT

Funzione diagonale non calcolabile

Problema della terminazione: dato ^ e ^, dire se ^ si ferma sull’input ^

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.6/13

Proprieta’ dei programmi

Proprieta’ funzionali: per ogni^ , o tutti i programmi in ^ hanno la proprieta’, o nessuno; almeno ha un programma ha la proprieta’, e almeno uno non ce l’ha

Le proprieta’ funzionali sono indecidibili (teorema di Post)

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.7/13

Riduzione

riducibile a se una soluzione di puo’

essere trasformata in una soluzione di Funzione Turing-calcolabile  tale che  ^ se e solo se 

  

riducibile a e decidibile decidibile

riducibile a , indecidibile indecidibile

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.8/13

Complessita’ computazionale

Analisi del caso pessimo Analisi asintotica

Notazione

Tutti i modelli formali dello stesso algoritmo hanno una complessita’ computazionale che e’ correlata da un polinomio

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.9/13

Classe P

MdT limitata polinomialmente

L decidibile polinomialmente (classe ^) La classe ^ e’ chiusa sotto il complemento Esiste almeno un linguaggio non in ^

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.10/13

Classe NP

Commesso viaggiatore, clique, ciclo Hamiltoniano, sottoinsieme-somma, soddisfacibilita’

Non si sa se sono in ^ o no

Risolvibili con MdT nondeterministiche limitate polinomialmente (almeno una

computazione limitata polinomialmente che accetta la stringa)

Non si sa se ^
 (si pensa che ^{ 
})

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.11/13

Riduzioni polinomiali

riducibile polinomialmente a ^, ^

calcolabile polinomialmente calcolabile polinomialmente

Tempo esponenziale per decidere , ridicibile polinomialmente a ^ tempo esponenziale per decidere ^

 e’ almeno difficile quanto

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.12/13

NP completezza

NP-completo: se in NP e se ogni linguaggio




e’ riducibile in tempo polinomiale a I problemi visti sono tutti riducibili

polinomialmente l’uno all’altro

Teorema di Cook: SAT e’ NP-completo

Corso di Automi e Linguaggi Formali – Gennaio-Marzo 2002 – p.13/13