Introduzione allo studio dell'informatica teorica

Corso: Materia:Informatica Teorica

Prossima lezione: Automa a stati finiti deterministico

Cenni storici sull'informatica teorica

L'informatica teorica è una disciplina che studia il concetto di computazione e ci si potrebbe riferire ad essa con il nome di teoria della computazione, come accade ancora oggi in diverse università britanniche e statunitensi.

Sebbene l'interesse per alcuni degli argomenti cardine dell'informatica teorica risalga a qualche millennio fa, lo studio sistematico ed organico della disciplina avviene da meno di un secolo.

Contrariamente ad altre materie, dove la storia delle origini si perde molto indietro nel tempo o è particolarmente sfumata, nel caso dell'informatica teorica esiste un evento scatenante: nel 1928 David Hilbert formulò il cosiddetto Entscheidungsproblem, in italiano problema di decisione; sinteticamente il problema consiste nel valutare se, a partire da un insieme di assiomi e da una proposizione matematica, esiste una procedura che permette di decidere meccanicamente se la proposizione può essere dedotta dagli assiomi oppure no.

Nel giro di otto anni venne pubblicata una serie di lavori che consentirono di rispondere negativamente allo stimolo proposto da Hilbert: i teoremi di incompletezza di Gödel, pubblicati nel 1931, pur non essendo direttamente collegati alla soluzione del problema di decisione gettarono qualche dubbio sul fatto che lo si potesse risolvere positivamente. In seguito, nel 1936 Alonzo Church ed Alan Turing pubblicarono indipendentemente due differenti risultati che avversarono definitivamente il problema di decisione.

I loro articoli diedero inizio allo sviluppo di due formalismi per la rappresentazione della computazione: il $\lambda$ calcolo di Curch e la macchina di Turing, oggi conosciuti come due tra i formalismi massimi.

Sebbene le idee dei due matematici siano equivalenti sul piano logico, la strategia seguita da Alan Turing di immaginare un dispositivo fisico in grado di svolgere computazioni automaticamente spinse i ricercatori a chiedersi se fosse possibile realizzarlo davvero. Qualche tentativo era stato compiuto, con fortune alterne, prima di allora: si ricordano in particolare la macchina analitica di Babbage e soprattutto la macchina di Leibnitz, che aveva introdotto l'impiego del sistema binario nelle calcolatrici. Il resto è storia recente: l'invenzione dei calcolatori, basati su modelli analoghi a quelli ideati da Turing, ha comportato una rapida evoluzione di tutti i settori coinvolti, con particolare attenzione per l'elettronica e per il software.

Tale sviluppo è sempre stato accompagnato, e spesso preceduto, da importanti studi nel settore dell'informatica teorica che costituisce, come conseguenza, le fondamenta del settore della computazione e funge da collante tra le applicazioni più disparate.

Il contesto della disciplina

Quando si inizia a studiare un nuovo argomento ha senso riflettere sul contesto in cui è inserito; non fa eccezione l'informatica teorica, per la quale vale la pena di spendere qualche parola.

La panoramica del corso ha sottolineato come l'oggetto di studio della disciplina sia il concetto di computazione che verrà studiato ed analizzato da diversi punti di vista.

La scomposizione del presente corso in tre moduli ci permette di strutturare la presentazione in tre parti: la prima centrata sul concetto di formalismo, la seconda sulle idee riguardanti la computabilità e la terza sulla complessità computazionale.

I formalismi

Indubbiamente, la necessità di valutare le qualità di un procedimento pensato per affrontare una computazione presuppone l'esistenza di un metodo che permetta di analizzarlo.

Vista l'attuale abbondanza di calcolatori elettronici digitali, macchine particolarmente adatte all'esecuzione di programmi che implementano algoritmi, che interesse può ancora esserci per lo studio dei formalismi? In un certo senso, specialmente la categoria degli automi è in buona sostanza un precursore dei moderni calcolatori; perché dunque affidarsi ad uno strumento che pare anacronistico?

I motivi sono tanti: il più significativo risiede nella sottile differenza tra quanto studiato dall'informatica teorica (la computazione) e quanto eseguito dai computer (i programmi); anche se un programma implementa uno o più algoritmi è molto importante non confondere il primo coi secondi.

Le prestazioni di un programma, infatti, dipendono in modo decisivo dallo hardware su cui viene eseguito, hardware che subisce continui aggiornamenti. Se affidassimo lo studio delle proprietà degli algoritmi ai programmi da essi derivati, le loro prestazioni cambierebbero quindi in modo importante nel tempo: basti pensare a come sono cambiate le prestazioni di un personal computer negli ultimi 30 anni!

É importante, quindi, riconoscere che si può parlare di prestazioni di un algoritmo anche in assenza di un programma che lo implementi; e qui nasce il problema: come si fa a rappresentare un algoritmo? Come si fa ad analizzare un algoritmo?

I metodi di rappresentazione si sprecano, uno su tutti i diagrammi di flusso; queste tecniche, tuttavia, sono state concepite allo scopo di comunicare il contenuto dell'algoritmo impiegando una notazione più o meno rigorosa, ma disinteressandosi degli aspetti analitici, di vitale importanza per stimare le prestazioni.

I metodi che consentono anche l'analisi, quindi, devono disporre di due caratteristiche: essere slegati dalle macchine commercialmente disponibili ed offrire a chi li utilizza tutti gli strumenti per trarre utili indicazioni in merito all'efficacia ed all'efficienza dell'algoritmo in questione.

La prima caratteristica, ossia l'indipendenza dallo hardware, si raggiunge per mezzo dell'astrazione, ossia pensando a strumenti di rappresentazione ed analisi tutt'altro che concreti; è proprio per questo motivo che i metodi che studieremo prendono il nome di formalismi.

La seconda caratteristica, ossia la funzionalità all'analisi, richiede una profonda conoscenza di cosa si intenda per caratteristiche e per prestazioni degli algoritmi e sarà premura di questo corso trattare tali aspetti.

Gli automi

Sebbene gli automi non siano gli unici formalismi possibili bisogna ammettere che questa categoria merita un discorso a parte.

Storicamente, infatti, è proprio lo studio degli automi che ha portato alla realizzazione dei primi calcolatori elettronici; il debito che la nostra società ha con Alan Turing, ad esempio, è altissimo proprio perché il suo formalismo principale, la macchina di Turing, contiene in sé tutti gli elementi dei moderni (e soprattutto dei futuri) calcolatori elettronici.

Vale davvero la pena, quindi, spendere due parole sulla struttura (piuttosto simile) che accomuna tutti gli automi: ognuno di essi può comunicare con l'ambiente e dispone anche di uno stato interno che cambia in funzione degli stimoli provenienti dal mondo esterno. Più precisamente, in ogni formalismo riconosciamo quattro componenti principali:

1. un ingresso che permette all'automa di acquisire dati dall'ambiente;
2. uno stato che indica l'attuale condizione operativa dell'automa;
3. un'uscita che consente all'automa di comunicare con l'ambiente;
4. un programma che coordina le attività dell'automa.

La teoria della computabilità

Il concetto di computazione è indissolubilmente legato a quello di problema; la sequenza delle azioni che si compiono durante una computazione può infatti essere interpretata come il procedimento seguito durante la soluzione di un problema.

Questa osservazione fa nascere alcune domande: che cos'è un problema? Sarà vero che ogni problema è associato ad una computazione? I vari formalismi che conosciamo possono risolvere gli stessi problemi?

La teoria della computabilità cerca di rispondere a questi interrogativi, offrendo una serie di strumenti concettuali utili per indagare le condizioni che portano all'esistenza di un algoritmo.

Il cuore della teoria della computabilità è il concetto di decidibilità: sinteticamente si può dire che un problema è decidibile quando esiste un algoritmo in grado di risolverlo.

Questo argomento è stato affrontato con strategie differenti da due matematici di grande spessore: Alonzo Church ed Alan Turing. Il primo ha affrontato lo studio della computabilità impiegando un approccio molto formale basato, come vedremo, sulle funzioni ricorsive parziali; il secondo ha preferito immaginare un dispositivo concettuale in grado di implementare gli algoritmi, creando la famosa macchina di Turing.

La teoria della computabilità si occupa esclusivamente dell'esistenza di un algoritmo e prescinde completamente dalle sue prestazioni, ossia non bada al modo in cui l'algoritmo in questione impiega le risorse a sua disposizione; questi aspetti saranno invece l'oggetto dello studio della teoria della complessità.

La teoria della complessità

In generale l'esistenza di un algoritmo non è sufficiente per renderlo utilizzabile: é possibile che richieda un quantitativo ingente di risorse o che fornisca i risultati in tempi troppo lunghi.

Affinché un algoritmo sia appetibile per le applicazioni pratiche deve fare un uso economico delle risorse a sua disposizione; in una parola, dev'essere efficiente.

L'attenzione all'efficienza porta con sé un'importante conseguenza: per analizzare l'impiego delle risorse è necessario anzitutto capire quali siano le risorse critiche per un algoritmo; è poi indispensabile trovare un modo per misurare il loro impiego.

La teoria della complessità cerca di dare una risposta a questi interrogativi, sviluppando strumenti utili per l'analisi degli algoritmi e per sviluppare previsioni ragionate sulle loro prestazioni in genere.

Il concetto di computazione

Fornire una definizione rigorosa di computazione è assai complicato poiché il concetto è complesso ed ogni definizione sarebbe in grado di descriverne bene alcune caratteristiche, trascurandone altre.

Proprio per questo motivo cercheremo una definizione intuitiva che ci permetta di apprezzare le qualità principali della computazione, rimanendo tuttavia aperti a possibili estensioni che ne approfondiscano il significato.

Sinteticamente possiamo dire che la computazione può essere pensata come un procedimento suddiviso in passi. Volendo essere un po' più rigorosi si potrebbe dire che la computazione è una successione finita o infinita di passi; si veda a tal proposito l'articolo di Leslie Lamport.

Descrivere la computazione significa quindi rappresentare la successione dei passi di cui si compone. Questa osservazione consente di porre l'accento sul concetto di passo; sempre secondo Lamport ci sono tre tecniche principali per la rappresentazione di un singolo passo: l'azione, lo stato oppure la coppia stato-azione. Nelle sezioni successive offriremo qualche dettaglio circa le tre modalità appena introdotte.

Il passo come stato

Sebbene il concetto di computazione sia molto astratto viene spesso impiegato per rappresentare in modo sintetico delle situazioni reali, ossia per costruire modelli.

La computazione è uno strumento prezioso per descrivere situazioni dinamiche, nelle quali vi siano caratteristiche che cambiano nello spazio oppure nel tempo.

Lo stato rappresenta la descrizione di una o più caratteristiche associate al sistema per cui si desidera costruire un modello.

Come al solito qualche esempio faciliterà la comprensione del concetto:

• in un semaforo lo stato potrebbe essere rosso, giallo o verde;
• in una lampadina lo stato potrebbe essere accesa o spenta;
• volendo studiare il livello di un lago lo stato potrebbe essere la sua profondità rispetto ad un riferimento dato.
• se il sistema fosse una particella con massa di 5 kg in moto rettilineo uniforme lo stato potrebbe essere una coppia $({\text{ posizione, quantità di moto}})$.

Se si sceglie di descrivere il singolo passo della computazione impiegando uno stato, l'intera computazione sarà una successione finita o infinita di stati. Anche in questo caso qualche esempio varrà più di mille parole:

• in qualche paese la successione degli stati per un semaforo sarà: $q_{n}$ = rosso, giallo, verde, giallo, rosso,...
• in altri paesi la successione potrebbe essere differente, ad esempio: $q_{n}$ = rosso, verde, giallo, rosso,...
• nel caso della lampadina la successione degli stati sarà: $q_{n}$ = spenta, accesa, spenta, accesa, ...
• nel caso della particella in movimento potrebbe avere senso considerare la successione $q_{n}$ = ( 0 m, 10 kg m/s ), (2 m , 10 kg m/s), (4 m, 10 kg m/s), ...

La descrizione di una computazione per mezzo del solo stato ammette un limite particolarmente sensibile: anche se si conosce l'esatta successione degli stati del sistema, non è sempre possibile dedurre quali azioni abbiano provocato i cambiamenti osservati.

In effetti vi sono situazioni in cui il passaggio tra due stati si può compiere svolgendo azioni diverse: disponendo della sola sequenza degli stati diventa impossibile dedurre quale azione abbia provocato l'evoluzione del sistema.

Si supponga, ad esempio, di considerare un sistema costituito da una lampadina che può essere azionata da due interruttori; la sequenza degli stati sarà sempre $q_{n}$ = spenta, accesa, spenta, accesa, ..., ma non sarà possibile risalire a quale interruttore abbia provocato il cambiamento di stato.

Proprio per questo motivo la descrizione della computazione come successione di stati non è sempre la soluzione migliore ed è possibile che si debbano prendere in considerazione strategie alternative.

Il passo come azione

Le azioni si possono interpretare come eventi che provocano un cambiamento dello stato di un sistema; da questa breve descrizione si può intuire il legame esistente tra le azioni e gli stati e si può comprendere come le azioni possano essere utilizzate per descrivere l'evoluzione del sistema stesso.

Quando la computazione costituisce il modello di un sistema reale le azioni da compiere sono facilmente deducibili dalle caratteristiche del sistema stesso. Come al solito presentiamo qualche esempio per chiarire le idee:

• nel caso di una porta le azioni sarebbero aprire e chiudere;
• nel caso di un'automobile in movimento le azioni potrebbero essere accendere, spegnere, accelerare, frenare, sterzare, avanzare, retrocedere;
• nel caso di una squadra di calcio le azioni possibili possono essere vincere, pareggiare, perdere.

Dopo aver identificato l'elenco delle azioni che possono manifestarsi la computazione può essere descritta come una successione di azioni. Vediamo qualche esempio:

• nel caso della porta: $a_{n}$ = aprire, chiudere, aprire, chiudere, ...
• nel caso dell'automobile: $a_{n}$ = accendere, avanzare, sterzare, accelerare, ...
• nel caso di una squadra di calcio: $a_{n}$ = vincere, vincere, perdere, pareggiare, vincere, ...

Descrivere una computazione tramite una successione di azioni ha un limite dettato dal fatto che è impossibile sapere qual è lo stato da cui inizia l'evoluzione della computazione stessa. Lo stato della computazione prima che vengano svolte azioni copre un'importanza particolare e prende il nome di stato iniziale; come vedremo questo concetto avrà un ruolo molto importante nella teoria degli automi.

Per chiarire il concetto si consideri l'esempio della squadra di calcio esaminato in precedenza; la stessa successione di azioni comporta risultati molto diversi a seconda che lo stato iniziale vedesse la squadra prima in classifica oppure ultima.

Il passo come coppia ${\text{( stato, azione )}}$

La descrizione della computazione come successione di stati presenta un limite dettato dall'assenza delle azioni; parallelamente, la descrizione della computazione come successione di azioni presenta un limite dettato dall'assenza dello stato iniziale.

Un buon modo per superare queste difficoltà consiste nel descrivere il singolo passo di una computazione come una coppia ordinata di elementi ${\text{( stato, azione )}}$.

Questo approccio risolve i problemi evidenziati in precedenza al costo di un lavoro di analisi più approfondito: anziché concentrare l'attenzione sull'elenco dei possibili stati oppure sull'elenco delle possibili azioni, in questo caso entrambi gli elementi vanno presi in considerazione.

Facciamo alcuni esempi:

• nel caso di una porta automatica: (chiusa, aprire), (chiusa, chiudere), (aperta, aprire), (aperta, chiudere);
• nel caso di un ascensore in un edificio a tre piani: (piano terra, salire), (piano terra, scendere), (primo piano, salire), (primo piano, scendere), (secondo piano, salire), (secondo piano, scendere);
• nel caso di un contamontete: (0 euro, inserire un euro), (0 euro, inserire 0.50 euro), (0.50 euro, inserire un euro), (0.50, inserire 0.50 euro), (1 euro, inserire un euro), (1 euro, inserire 0.50 euro), (1.50 euro, inserire 0.50 euro);

Descrivere una computazione come una successione di coppie (passo, azione) porta a risultati simili a quelli riportati di seguito:

• porta automatica: (aperta, chiudere), (chiusa, aprire), (aperta, aprire), (aperta, chiudere), ...;
• ascensore: (piano terra, scendere), (piano terra, salire), (primo piano, salire), (secondo piano, scendere), ...;
• contamonete: (0 euro, inserire un euro), (1 euro, inserire 0.50 euro), (1 euro, inserire 0.50 euro);

Questa situazione è quella che descrive la computazione in modo più dettagliato, poiché per ogni passo della computazione si conoscono sia lo stato attuale, sia l'azione che verrà compiuta e che porterà, quindi allo stato prossimo.

Un esempio completo

Questa sezione ha lo scopo di mettere in pratica i concetti appena introdotti per la computazione affrontando la soluzione di un problema di geometria.

Supponiamo di voler calcolare l'area di un rettangolo conoscendo il suo perimetro e la lunghezza di uno dei lati.

Le sezioni seguenti presenteranno tre possibili computazioni, ognuna pensata come successione di stati descritti nelle modalità discusse in precedenza.

Computazione come successione di azioni

Indichiamo con $a_{n}$ la successione che descrive la sequenza di azioni necessaria per attuare la computazione desiderata. Potremo scrivere:

1. $a_{1}$: dimezzare;
2. $a_{2}$: sottrarre;
3. $a_{3}$: moltiplicare.

La scarsa comunicatività della tecnica di rappresentazione basata su azioni è qui evidente; inoltre, per poter sapere cosa accade basterebbe conoscere lo stato iniziale della computazione, esattamente come già discusso in precedenza.

Computazione come successione di stati

Supponiamo di voler rappresentare la computazione impiegando una successione di stati anziché di azioni.

Indichiamo con $q_{n}$ la successione che descrive la sequenza di stati necessaria per attuare la computazione desiderata. Potremo scrivere:

1. $q_{1}$: perimetro;
2. $q_{2}$: semiperimetro;
3. $q_{3}$: lunghezza del lato mancante;
4. $q_{4}$: area.

Questa descrizione è senz'altro più descrittiva della precedente; tuttavia la mancanza delle azioni costringe a dedurle in base alla successione degli stati.

Computazione come successione di coppie ${\text{(stato, azione)}}$

Indicando con $p_{n}$ la successione che indica la sequenza di transizioni necessarie per attuare la computazione desiderata potremo scrivere:

1. $p_{1}$: (perimetro, dimezzare)
2. $p_{2}$: (semiperimetro, sottrarre)
3. $p_{3}$: (lunghezza del lato mancante, moltiplicare)

Come si può notare confrontando le tre situazioni, questa tecnica di rappresentazione è indubbiamente la più espressiva in quanto in ogni passo si conosce lo stato attuale e l'azione che verrà compiuta.

Vista la buona qualità di questa rappresentazione, in generale la preferiremo alle altre.

Il concetto di transizione

Abbiamo visto che la tecnica che prevede di descrivere la computazione impiegando coppie ordinate $({\text{stato, azione}})$ è particolarmente espressiva e permette di risalire a gran parte delle informazioni coinvolte nella computazione stessa.

Nonostante ciò la descrizione è ancora incompleta in quanto in ogni passo della procedura si conoscono lo stato attuale e l'azione, ma non si conosce lo stato prossimo, ossia lo stato in cui ci si troverà dopo aver svolto l'azione. Per ovviare a questo inconveniente si possono impiegare due strategie: concepire lo stato prossimo come un'entità calcolata a partire dallo stato attuale e da un'azione oppure descrivere ogni passo come una tripla ordinata di elementi, in cui il primo è lo stato attuale, il secondo è l'azione ed il terzo è lo stato prossimo.

L'insieme dello stato attuale, dell'azione e dello stato prossimo prende il nome di transizione e va pensata come la trasformazione subita dalla computazione per opera di un'azione.

Vediamo come si rappresentano le transizioni impiegando entrambe le strategie, basandosi sull'esempio del calcolo dell'area del rettangolo esaminato poc'anzi.

La transizione come funzione

È possibile immaginare che esista una funzione che permette di calcolare lo stato prossimo della computazione conoscendo lo stato attuale e l'azione da svolgere. Indicando con la lettera $f$ una tale funzione e con $t_{n}$ la successione delle transizioni, la computazione riguardante il calcolo dell'area del rettangolo diventerebbe:

1. $t_{1}$ = semiperimetro = f(perimetro, dimezzare);
2. $t_{2}$ = lunghezza lato mancante = f(semiperimetro, sottrarre);
3. $t_{3}$ = area = f(lunghezza lato mancante, moltiplicare).

Grazie a questa tecnica di rappresentazione delle transizioni è possibile sintetizzare l'intera computazione in un passaggio solo:

$area=f(\underbrace {f(\overbrace {f(perimetro,dimezzare)} ^{semiperimetro},sottrarre)} _{lato},moltiplicare)$

Come si può notare, nella rappresentazione sintetica della computazione appena esposta compaiono solamente lo stato iniziale e la sequenza delle azioni da svolgere.

Si può anche notare come la discussione sia stata, per ora, fortemente informale: abbiamo introdotto una funzione matematica senza parlare né del suo insieme di partenza, né tantomeno dell'insieme di arrivo. L'intento in questo paragrafo é la presentazione intuitiva della tecnica impiegata per la rappresentazione delle transizioni, lasciando ad un momento successivo una sistemazione più rigorosa dei dettagli.

La transizione come tripla ordinata

Adottando questa strategia per la rappresentazione delle transizioni ed indicando con $t_{n}$ la successione delle transizioni, è possibile descrivere la computazione come segue:

1. $t_{1}$ = (perimetro, dimezzare, semiperimetro);
2. $t_{2}$ = (semiperimetro, sottrarre, lato mancante);
3. $t_{3}$ = (lato mancante, moltiplicare, area).

La tecnica precedente ha l'innegabile vantaggio di essere più facile da applicare a livello di calcolo; la tecnica attuale, tuttavia, ha il pregio di essere molto descrittiva e sarà usata, nella prossima lezione, per introdurre una modalità di rappresentazione per gli automi a stati finiti.

Bibliografia

In questa sezione viene presentata una bibliografia essenziale e generale, ossia in grado di coprire tutti gli argomenti trattati nel corso. Nelle singole lezioni, invece, verranno proposti riferimenti bibliografici più specifici, da interpretare come letture di approfondimento.

• Dino Mandrioli, Informatica teorica, Milano, CittàStudi, 1999, ISBN 978-8825172416.
• Michael Sipser, Introduction to the theory of computation, Boston, Course Technology Ptr, 2012, ISBN 978-1133187790.

Corso: Materia:Informatica Teorica

Prossima lezione: Automa a stati finiti deterministico