Appunti completi corso Principi dell'informatica

(F G) F ≡ F

∨ ∧

(F G) F ≡ F

∧ ∨ ∧ ∨ ∧

F (G H) ≡ (F G) (F H)

∨ ∧ ∨ ∧ ∨

F (G H) ≡ (F G) (F H)

¬¬F ≡ F

∧ ∨

¬(F G) ≡ ¬F ¬G

∨ ∧

¬(F G) ≡ ¬F ¬G

∧

F ↔ G ≡ (F → G) (G → F)

∨

F → G ≡ ¬F G

F → G ≡ ¬G → ¬F

Le equivalenze si studiano sostanzialmente per riscrivere pezzi di formula in modo più

semplice. Se abbiamo due formule equivalenti possiamo sostituire una formula all'interno

di un'altra senza cambiare la tabella di verità. Inoltre per ottenere una certa tabella di

verità non è per forza necessario avere a disposizione tutti i connettivi logici. L'insieme

{not, and} è FUNZIONALMENTE COMPLETO perché può simulare il comportamento di

tutti gli altri connettivi. Anche gli operatori logici {nand} e {nor} formano da soli un insieme

funzionalmente completo.

Ogni formula può essere indicata in FORMA NORMALE CONGIUNTIVA o FORMA

NORMALE DISGIUNTIVA. Equivalgono esattamente alle forme canoniche somma di

prodotti e prodotto di somme che abbiamo visto in ACSO.

Noi sappiamo che si può passare da una forma logica ad un'altra equivalente. È possibile

effettuare questo passaggio computazionalmente? I CALCULI sono un insieme di assiomi

e regole di inferenza che permettono questo passaggio. Questi elementi forniscono una

relazione di derivabilità tra due formule. Diciamo che F |-- G se è possibile passare da F a

G usando solo questi assiomi e regole di inferenza. Idealmente la relazione di derivabilità

dovrebbe essere SOUND (ovvero se F |-- G allora F |= G) e COMPLETA (ovvero se F |=

G allora F |-- G).

La logica delle proposizioni ha tante applicazioni, ma la sua potenza espressiva è limitata.

È qui che arriva in soccorso la LOGICA DEL PRIM'ORDINE o LOGICA DEI PREDICATI

che è una sua estensione. Questa logica infatti si estende considerando OGGETTI,

PROPRIETÀ/RELAZIONI e FUNZIONI.

L'alfabeto della logica del prim'ordine è composta da:

Un set infinito e numerabile di variabili X, Y, Z...

– Un set di simboli di funzioni f, g...

– Un set di simboli di relazioni p, q, r...

– ∧ ∨

I connettivi logici ¬ → ↔

– ∃ ∀

I quantificatori

– I simboli di punteggiatura ( ) ,

–

Ogni funzione e simbolo di relazione ha una sua ARIETÀ, cioè il numero di argomenti che

richiede. La scritta p/n dice che il simbolo p richiede n argomenti. Le funzioni con zero

argomenti si chiamano COSTANTI. I predicati con zero argomenti si chiamano

PROPOSIZIONI. Quindi la logica delle proposizioni aveva predicati senza argomenti.

Gli argomenti delle funzioni sono detti TERMINI. I termini sono definiti ricorsivamente

come una singola variabile oppure, se ho una funzione n-aria f/n e l'insieme t , t ...t è

1 2 n

composto da termini, allora anche f(t , t ...t ) è un termine. Quest'ultimo viene chiamato

1 2 n

anche FORMULA ATOMICA. Le altre formule sono applicazioni dei connettivi logici e dei

quantificatori agli atomi.

Nella traduzione di frasi in logica dei predicati bisogna considerare due cose:

∀

Il quantificatore è usato insieme a →

– ∃ ∧

Il quantificatore è usato insieme a

–

Nella lezione sugli automi a pila abbiamo visto che ci sono linguaggi che non possono

riconoscere, perché la famiglia di linguaggi riconosciuti non è chiusa rispetto all'unione. Un

n n n n n n 2n

PDA non può per esempio interpretare i linguaggi a b c e a b unione a b . Questo

perché lo stack è una memoria distruttiva: quando un dato viene letto viene anche

rimosso. È necessaria una macchina con memoria persistente, ciò che è la MACCHINA DI

TURING. È il primo modello più vicino ai computer attuali, e dispone di una memoria

permanente che può essere letta più volte in qualsiasi momento, in qualsiasi direzione.

Le macchine di Turing sono composte in modo simile agli automi precedenti: hanno un

nastro di ingresso, eventualmente uno di uscita e uno o più nastri di memoria con un

numero di celle idealmente infinito, dove indichiamo con un apposito simbolo, per esempio

␢, che sono vuote. Le mosse di una macchina di Turing sono composte da un simbolo

letto in ingresso, da un numero K di simboli (uno per ogni nastro di memoria) e dallo stato

attuale. Le azioni che si possono fare sono cambiare stato, sovrascrivere i K simboli sui

nastri di memoria e spostare la testina su di essi. Lo spostamento può avvenire in tre

modi: a sinistra (L), a destra (R) o stare fermi (S). Il tipo di spostamento va indicato

esplicitamente e si può fare anche sul nastro di ingresso! Sulle transizioni quindi si

scriverà i, <A , A ..A > / <A ', A '...A '>, <M , M , M ...M > dove i è il simbolo in ingresso,

1 2. n 1 2 n 0 1 2 n

A è il simbolo presente sul k-esimo nastro, A ' è il simbolo da rimpiazzare sul k-esimo

k k

nastro mentre M è lo spostamento da fare sul k-esimo nastro. M è lo spostamento sul

k 0

nastro di ingresso. È da far notare che, mentre i PDA possono scrivere più simboli sullo

stack, le macchine di Turing possono scrivere solo un carattere alla volta sui nastri di

memoria.

Le formalizzazioni se non strettamente necessarie non le facciamo perché mi hanno rotto.

Sulle macchine di Turing bisogna precisare due cose: non esistono le epsilon mosse e

la lettura delle stringhe termina non appena si raggiunge uno stato finale! Quindi

bisogna fare attenzione a questi aspetti per mettere gli stati giusti... e si può arrivare in uno

stato finale senza che la macchina abbia letto tutta la stringa! Ecco l'esempio di una

n n n

Macchina di Turing che legge il linguaggio a b c :

I linguaggi interpretati da una macchina di Turing ovviamente comprendono anche quelli

dei PDA (basta usare la memoria come se fosse uno stack) e si chiamano ENUMERABILI

RICORSIVAMENTE.

Le macchine di Turing sono formalmente uguali a quelle di Von Neumann, che

rappresentano i computer attuali. La differenza sta nell'accesso alla memoria che per

Turing è sequenziale mentre per Von Neumann è ad accesso casuale. Questo rende la

macchina di Von Neumann più veloce ma ha lo stesso potere espressivo.

I linguaggi delle macchine di Turing sono chiusi rispetto a intersezione, unione,

concatenazione, stella di Kleeni ma NON rispetto al complemento e alla differenza!

Questo avviene principalmente perché le macchine di Turing hanno il problema di poter

non terminare mai la lettura e di finire in loop eterno (proprio come i nostri computer lelz).

Facendo il complemento di un linguaggio potremmo ottenerne uno che ha questi loop e

che non portano alla condizione di accettazione richiesta per il complemento.

Anche le macchine di Turing ovviamente possono avere un nastro di uscita e comportarsi

come traduttori (in cui però il nastro di uscita può solo muoversi a destra e star fermo, non

muoversi a sinistra), e come detto prima hanno la stessa espressività di una macchina di

Von Neumann, in quanto l'unica differenza è il tipo di accesso alla memoria. È una

macchina che concettualmente è molto semplice, ma progettarle non lo è altrettanto. Si

vede benissimo nell'esempio in cui bisogna semplicemente incrementare un numero di 1 :)

Esistono centinaia di varianti della macchina di Turing, ma tutte quante hanno lo stesso

potere espressivo. Esiste persino una variante detta A NASTRO SINGOLO in cui si usa

un solo nastro come input, memoria e uscita! E nonostante ciò riesce a esprimere tutti i

linguaggi che sanno codificare le altre macchine di Turing (ovviamente richiede un numero

enorme di passi ma ce la fa). In queste macchine l'unico nastro viene considerato illimitato

da entrambi i lati, dato che invece negli altri modelli i nastri erano infiniti da un lato ma

avevano un punto di partenza ben definito.

Altre varianti hanno per esempio dei nastri a matrice, per cui i movimenti non sono solo in

due direzioni ma ben otto, perché puoi andare sopra, sotto, a destra, a sinistra e negli

angoli. Nonostante tuta questa varietà, si può dimostrare (per fortuna non lo facciamo) che

tutti questi modelli sono tra loro equivalenti dal punto di vista espressivo. Ciò che cambia

naturalmente è l'efficienza (una macchina di Turing a nastro singolo richiede numerosi stati

e transizioni in più rispetto a una tradizionale).

Tutti i modelli visti finora sono DETERMINISTICI, ovvero ad ogni input esiste una ed una

sola transizione ben definita. Ci sono dei casi però in cui ad un certo input non sappiamo

quale sia la strada giusta per arrivare alla soluzione, e dobbiamo quindi “scegliere” una

strada. Per esempio, se dobbiamo fare una macchina di Turing che riconosca se un

numero è divisibile per 4 leggendo le cifre da sinistra, ci serve sapere quali sono le ultime

due cifre del numero. Ma mentre leggiamo le cifre non possiamo sapere se quella che

stiamo ricevendo è già la penultima, l'ultima o una nel mezzo, quindi ci tocca “indovinare”

in quale situazione ci troviamo. Questa situazione si chiama NON DETERMINISMO e

graficamente si rappresenta con delle transizioni a diversi stati con lo stesso input. Nella

pratica è come se avessimo più thread che prendono strade diverse.

La funzione di transizione δ nelle macchine non deterministiche non è più una funzione nel

senso tradizionale del termine, perché non porta da un input ad uno stato ben preciso, ma

porta ad un insieme di stati possibili, chiamato INSIEME DELLE PARTI. Nella funzione δ*

che, dato un input ritorna tutto il percorso, lo stato d'arrivo diventa l'unione di tutti gli stati

d'arrivo. La CONDIZIONE DI ACCETTAZIONE è che almeno uno dei percorsi possibili

porti ad uno stato di accettazione.

Ci chiediamo qual è la differenza espressiva tra gli automi deterministici e quelli non,

iniziando dagli automi a stati finiti. Beh, tra un DFSA e un NDFSA non cambia proprio

nulla! Dato un automa a stati finiti non deterministico possiamo tradurlo in una versione

deterministica. Per farlo basta raggruppare gli stati d'arrivo in un unico statone e definiamo

le transizioni per questo statone. Se nell'insieme di arrivo c'è uno stato d'arrivo, anche lo

statone sarà uno stato d'arrivo. Il problema è che questo lavoro, oltre a essere noioso da

mandarti ai pazzi, rende l'automa deterministico con una quantità di stati enorme, con un

aumento esponenziale nel cas