Algoritmi e principi dell'Informatica

Classificazione delle grammatiche

Un elemento di una grammatica sarà indicato come X e sarà detto assioma o simbolo iniziale.

Data una grammatica si definisce su di essa la relazione binaria di derivazione immediata, indicata come →.

Il linguaggio generato da una grammatica è costituito da tutte e sole le stringhe di soli simboli terminali, che possono essere derivate a partire dal simbolo iniziale applicando un qualsiasi numero di sostituzioni.

1. CLASSIFICAZIONE

Tipo 0: non ci è alcuna limitazione nel tipo di produzione

Tipo 1: introduciamo il vincolo che le produzioni siano solamente della forma D → AB, dove A è un simbolo non terminale

Tipo 2: se per ogni produzione si verifica che la stringa di sinistra ha lunghezza minore o uguale alla stringa di destra

Tipo 3: se per ogni produzione A → aB, dove a è un simbolo terminale e B è un simbolo non terminale

2. GRAMMATICHE E AUTOMI

Dato un automa a stati finiti (AF), è possibile associare ad esso una grammatica.

è possibile costruire una grammatica regolare (tipo 3) ad essoA,equivalente, ossia in grado di generare lo stesso linguaggio riconosciuto da e viceversa.A,• Dato un APN automa a pila non deterministico è possibile costruire una grammatica non contestualeG A,(tipo 2) ad esso equivalente, ossia in grado di generare lo stesso linguaggio riconosciuto da eviceversa.• Le grammatiche di tipo 1 sono formalismi equivalenti agli automi lineari limitati, una versione ristretta dimacchina di Turing MT a nastro singolo, in cui solo una parte del nastro contigua alla stringa in ingressopuò essere letta o scritta dalla testina.• Le grammatiche non ristrette (tipo 0) sono equivalenti a macchine di Turing usate come accetto richieste diG Mlinguaggi; ovvero, per ogni grammatica non ristretta esiste una MT che accetta lo stesso linguaggiog,generato da e viceversa.LA RISOLUZIONE AUTOMATICA DEI PROBLEMIDopo aver esaminato modelli atti a descrivere problemi di

elaborazione delle informazioni (automi e grammatiche), vogliamo studiare in modo sistematico quali problemi possono essere affrontati e risolti mediante "macchine da calcolo".

Per iniziare, riassumiamo alcune conclusioni alle quali siamo arrivati:

Automi e grammatiche, pur essendo modelli matematici, si possono considerare dispositivi meccanici per la risoluzione di problemi; spesso un problema matematico costituisce la formalizzazione di qualche problema pratico.

Alcuni formalismi sono più potenti di altri, ossia sono in grado di riconoscere (o generare, o comunque definire) alcuni linguaggi che altri formalismi non possono accettare, oppure riescono ad implementare traduzioni non effettuabili da un altro formalismo.

Nessun formalismo fra quelli considerati è più potente delle macchine di Turing MT.

Le nozioni richiamate fanno sorgere spontaneamente alcune domande:

I formalismi esaminati sono effettivamente adatti a rappresentare un risolutore

meccanico di problemi? La capacità di risolvere meccanicamente i problemi dipende dal modo in cui vengono formalizzati?

Esistono formalismi di calcolo più potenti delle MT?

Una volta che un problema è stato opportunamente formalizzato, è sempre possibile risolverlo mediante una procedura meccanica?

1. FORMALIZZAZIONE DEL CONCETTO DI PROBLEMA

Abbiamo già notato che molti problemi si possono opportunamente descrivere come riconoscimento di linguaggi o come traduzione da un linguaggio ad un altro o come calcolo di una determinata funzione.

Osserviamo che ogni problema matematicamente formalizzato è descrivibile in una di queste forme, alla sola condizione che il dominio del problema sia un insieme numerabile; in tal caso i suoi elementi si possono mettere in corrispondenza biunivoca con gli elementi di N.

Di conseguenza, il problema originale si può riformulare come il problema del calcolo di una funzione f: N -> N, come una

Traduzione o come un riconoscimento di linguaggio. Tutti i formalismi matematici esaminati finora sono discreti, ovvero sono dotati di domini matematici numerabili, definiti in modo finito; notiamo che questa informazione è perfettamente in accordo con la tecnologia digitale dei moderni calcolatori.

Ricordiamo: ogni MT è equivalente ad un'opportuna MT avente un alfabeto con due soli simboli; possiamo quindi affermare che la classe di problemi risolvibili dalle MT risulta indipendente dall'alfabeto scelto per la rappresentazione, purché contenga almeno due elementi.

Conclusione: le MT sono i risolutori meccanici di problemi più potenti fra quelli incontrati finora, indipendentemente dalla codifica del problema. Questo fatto consente di concentrare l'attenzione sulle MT intese come risolutori di problemi, senza preoccuparsi della formalizzazione scelta per la nozione di problema.

2. TESI DI CHURCH

LINGUAGGI DI PROGRAMMAZIONE E MACCHINE DI TURING

M,• Data una MT è possibile costruire un programma Pascal o C che simuli purché il calcolatore cheesegue il programma disponga di una quantità di memoria sufficientemente grande da non causare alcunoverflow durante l’esecuzione.

• Dato un programma Pascal o C è possibile costruire una MT che calcoli la stessa funzione calcolata dalprogramma.

Si è dunque scoperto che le MT hanno la stessa potenza di calcolo non solo delle grammatiche non ristrette,ma anche dei programmi sviluppabili nei consueti linguaggi di programmazione ad alto livello.

Conclusione: tutti i formalismi noti per modellati dispositivi di calcolo discreti hanno, al più, la stessa potenzadelle macchine di Turing.

Tesi di Church: non esiste alcun formalismo, per modellare una determinata computazione meccanica, chesia più potente delle MT e dei formalismi ad esse equivalenti.

In base a tale enunciato, poiché non esistono formalismi più potenti delle MT,

ALGORITMI

Intuitivamente, gli algoritmi si possono intendere come un metodo astratto di descrizione dei programmi eseguibili da un calcolatore; un tale programma è una sequenza di comandi che, una volta eseguita dal calcolatore, può risolvere un determinato problema.

Un algoritmo rappresenta la sequenza astratta di operazioni elementari che risolvono un problema in modo meccanico.

indipendentemente dal particolare processore (o linguaggio di codifica) scelto.

• Un algoritmo deve contenere una sequenza finita di istruzioni.
• Deve esistere un agente (processore) che sia in grado di comprendere univocamente le istruzioni e di eseguirle producendo risultati precisi e prevedibili.
• Il processore è dotato di dispositivi di memoria in cui possono essere immagazzinati i risultati intermedi.
• La computazione è discreta e non esiste limite al numero di passi richiesti per effettuare un calcolo.
• Gli algoritmi vengono eseguiti deterministicamente.
• Non esiste un limite finito sui dati di ingresso e di uscita.
• Non c'è limite alla quantità di memoria richiesta per effettuare i calcoli (se la memoria di un calcolatore non è riempita completamente durante un calcolo, si può supporre che sia illimitata rispetto a quel calcolo).

Tesi di Church: ogni algoritmo per la soluzione automatica di un problema può essere eseguito da una macchina di Turing.

problema può essere codificato in termini di una MT (o di un formalismo equivalente).

3. ENUMERAZIONE E MACCHINE DI TURING UNIVERSALI

Finora le MT sono state studiate in qualità di dispositivi che sono in grado di risolvere un particolare problema, definito dalla funzione di transizione. Per questo motivo, le macchine di Turing si possono considerare come calcolatori astratti, specializzati e non programmabili; una volta caricato il programma nella memoria di sola lettura del calcolatore, la macchina può eseguire solo quel programma.

ENUMERAZIONE enumerato algoritmicamente

S, S

Dato un qualsiasi insieme può essere se è possibile stabilire una S N.

biiezione fra e l'insieme dei numeri naturali

A MT

Fissiamo ora un alfabeto e consideriamo l'insieme delle MT a nastro singolo e senza stati finali, aventi

A MT N <-> MT

come insieme di simboli. Mostriamo come possa essere enumerato, ovvero definire : .

E A

k A k

Per ogni intero esiste un numero finito di MT,

aventi come insieme di simboli ed esattamente di nastri.Infatti, il numero di modi diversi in cui si può definire la funzione di transizione fissato l'alfabeto e il numero distati risulta finito, poiché ha dominio e condominio finito. dif: D -> R, D R f

In generale, data una funzione con e finiti vi sono esattamente funzioni totali diverse.

IRISeguendo lo stesso ragionamento per le MT, poiché la funzione di transizione è definita comeQ A -> Q A L, S},: x x x {R, esisteranno esattamenteo lQlilAIIQI.la1 13 macchine di TuringA Qaventi come insieme dei simboli e come spazio degli stati. n.ieh A, kSe chiamiamo la cardinalità dell'insieme allora esistono MT dotate di stati.h.ie1 3MT kPer poter enumerare le MT in è ora necessario ordinare le MT a stati seguendo un preciso criterio, adAesempio in base all'ordine lessicografico, stabilendoq < q < ... < q blank = a < a < ... < a R < L < S◦ 0 1 k-1 0 1 h-1(q,