INFORMATICA: SALTO NEL VUOTO?

Informatica: salto nel vuoto?

Il titolo del saggio è solo in apparenza fantasioso e, pertanto, occorre in qualche modo chiarirlo. Il salto nel vuoto si riferisce al senso di spaesamento generato dai continui balzi in avanti, verso la prossima futura applicazione, che l’informatica ha compiuto fin dagli inizi. La sua popolarità è in costante aumento. Infatti l’informatica oggi facilita la pressoché istantanea comunicazione di ogni tipo di evento che interessi l’umanità, sia globalmente sia individualmente. Scienziati, industriali e commercianti annunciano continuamente e offrono novità, la cui importanza è molto difficile da valutare, in quanto riguardante sia nuovi rimedi, sia pericoli da evitare (se possibile) o svaghi con immediato godimento. Riassumendo, la domanda riflette la naturale sorpresa che ciascuno di noi prova nel cercare di definire il preciso significato attuale della parola informatica; ne sarà proposto uno nel prosieguo della trattazione.

La possibile soluzione di problemi attuali, quale il riscaldamento globale, o il raggiungimento di obiettivi auspicabili, ma al momento apparentemente fuori dalla nostra portata, quali lo sviluppo sostenibile, l’economia verde, le fonti di energia rinnovabili possono essere ricondotti all’espressione ‘salviamo la vita sulla Terra’; allo stesso modo, la comune essenza del metodo risolutivo di ciascuno dei problemi appena enunciati può essere riassunta in modo molto conciso mediante l’espressione ‘unifichiamo il linguaggio umano con quello degli algoritmi’.

Prima di procedere oltre, conviene evidenziare il significato dei termini informatica e algoritmo. Con il primo intendiamo la scienza, e le tecniche a essa connesse, dell’elaborazione dei dati; con il secondo s’intende una procedura per la soluzione di un problema.

L’espressione ‘unifichiamo il linguaggio umano con quello degli algoritmi’ è chiaramente un problema. Esisterà davvero un algoritmo per la soluzione di tale problema? La minaccia è che esso non abbia mai termine ovvero che tale problema non abbia soluzione. Ciò succede spesso quando un’entità ha a che fare con sé stessa, come vedremo. Tuttavia non dobbiamo disperare. In certi casi, nonostante abbiamo la dimostrazione dell’inesistenza della soluzione, un teorema di Gödel viene in nostro soccorso, come ben presto sarà chiarito. Si deve, in qualche modo, riuscire a interrogare il computer.

Ma il problema di fondo è l’importanza della domanda rispetto alla risposta. Tale approccio impone proprio una metafora: il colloquio uomo-macchina. Tale metafora si addiceva, forse, all’uso del computer nei primi dieci anni della sua esistenza (per es., per generare tavole di tiro). Proseguendo con la metafora, si può dire che ben presto il computer si è appropriato della manipolazione delle immagini bi- e tridimensionali, fornendo, in questo nuovo secolo, per es., la stampante tridimensionale.

È chiaro, tuttavia, che inseguire le singole scoperte non ci porta poi molto lontano. La domanda allora dovrebbe essere formulata nella maniera più generale possibile, in modo da lasciare il più alto grado di libertà alla risposta. Sembra che tale strategia ignori un fatto importante, reso tanto più visibile quanto più si limiti la portata della risposta. Vediamo cosa accade se la domanda prevede come risposta un sì o un no. È naturale associare la parola ‘vero’ al sì e la parola ‘falso’ al no.

Nel 1931, il logico matematico Kurt Gödel sconvolse il mondo dei suoi colleghi con il teorema di incompletezza, che ammetteva l’esistenza di teoremi ‘veri’ ma non dimostrabili. Questo teorema non è da considerare una sconfitta per i logici. La paura del paradosso ha spinto alcuni logici (primo fra tutti Bertrand Russell) a creare la teoria dei tipi, tendente a limitare la potenza dei formalismi. Invece Gödel ha sfruttato i paradossi, aprendo vie illimitate alla creatività di nuovi risultati formali in logica matematica e quindi applicabili in informatica.

Il logico Alan M. Turing (1912-1954), inventore dell’omonima macchina, sfruttandone l’universalità ha cercato di aiutare la fantasia dei logici; ma il suo tentativo ha riscosso risultati concreti non estrapolabili, purtroppo, dal punto di vista metodologico.

Tutto è virtuale: il computer, l’immaginazione

Quanto finora detto introduce quella che è stata chiamata realtà virtuale, concetto provocato dall’esistenza di computer, di filosofi della scienza e, per contagio, da quella degli esistenzalisti e degli entusiasti della filosofia morale e religiosa. Si consideri la pubblicazione nel 1957 del libro di Martin Gardner Fads and fallacies in the name of science (trad. it. Nel nome della scienza, 1998) con il provocatorio sottotitolo: The curious theories of modern pseudoscientists and the strange, amusing and alarming cults that surround them. A study in human gullibility.

Una soluzione più realista anche se più ironica, ma in armonia con gli ultimi progressi dell’informatica, in questo scorcio di nuovo secolo, è quella di trarre profitto della realtà virtuale utilizzando una nuova definizione: tuttologia formale. Si tratta di un’espressione introdotta dall’autore di questo saggio. Ci limitiamo qui a riassumere la teoria dei molti universi, dovuta all’astrofisico Dennis W. Sciama (1926-1999) che, parlando dell’universo che conosciamo, in armonia con la nascita della vita, con l’evoluzione dell’uomo e della sua intelligenza, e con tutti i parametri cosmologici, astronomici, fisici e chimici che appaiono modulati in funzione della nostra specie, si domanda se ciò sia dovuto al caso o alla mano di Dio, preferendo credere che il nostro sia soltanto uno degli infiniti universi esistenti, ciascuno con caratteristiche sue proprie e inaccessibili tra loro. In questo nostro universo si è formato l’uomo. In altri universi, forse, esistono creature diversissime da noi. Tale considerazione appare la giusta reazione di un eccellente cosmologo alla tuttologia formale, con la quale vengono eliminate in un solo colpo le trascendenze prive di carattere matematico, fisico, chimico o di scienze naturali. Per quanto riguarda l’informatica e soprattutto il ruolo dell’informatico, che vuole tradurre nel modo più semplice, ma anche più generale, le informazioni ricavate da esperimenti in procedure previsionali, l’ipotesi più minacciosa di Sciama è l’infinità degli universi. È abbastanza intuitivo che un computer, per condurre a termine una procedura, deve assolutamente evitare sia l’infinità della durata di un calcolo sia l’infinità degli oggetti con cui venire a contatto. In questa parte del saggio non pretendiamo che il lettore conosca i formalismi che saranno descritti in seguito. Possiamo però sottolineare la forte analogia tra avvenimenti della storia dell’informatica teorica nel trentennio 1950-1980 e situazioni alquanto particolari e preoccupanti che possono accadere durante la nostra stessa vita.

Riprendiamo, dunque, il problema del computer che deve evitare sia l’infinità della durata del calcolo sia l’infinità degli oggetti contattati sui quali deve operare. Una soluzione brillante, ma pericolosa, è che il computer dia la precedenza a quegli oggetti che gli sono più vicini. Nulla è più vicino a esso che una sua parte. Questa constatazione appare molto banale, ma lo è molto meno se la confrontiamo con certe azioni della nostra vita. Operare su una parte di noi stessi può essere molto pericoloso, per noi. Suicidio? Non necessariamente: se applichiamo questa operazione ai nostri simili, a coloro che risultano a noi più vicini o di cui ci sentiamo responsabili, possiamo causare uno dei seguenti fenomeni: fuoco amico, conflitto di interessi, scegliere sé stesso come avvocato difensore in una causa in cui si è uno fra gli imputati.

Tali fenomeni sembrano possedere un inevitabile carattere paradossale. Ebbene, in seguito, necessariamente in maniera più pragmatica, condivideremo con il lettore il piacere di superare questi pericoli e difficoltà senza dover imporre alcuna disciplina di tipi oppure simili restrizioni!

Si è appena accennato a particolari problemi che il computer deve risolvere per poter soddisfare le pretese descritte nell’introduzione di questo saggio. Non possiamo dimenticare la più importante di esse. Il computer ci deve aiutare a risolvere i problemi citati per contribuire alla necessità di salvare la vita sulla Terra. Il computer deve poter assimilare e utilizzare le conoscenze sul binomio vita-morte in biologia. È quindi saggio imitare la natura, che si avvale della procedura chiamata apoptosi, equivalente a una condanna a morte di una cellula malata che potrebbe infettare le sue vicine. Siamo arrivati dunque alla seguente domanda: qual è l’apoptosi informatica?

Questa domanda, che rasenta il nonsenso, ha importanti motivazioni. Per es., è essenziale per evidenziare l’estrema rilevanza assunta dall’informatica in questi ultimi vent’anni per limitare – o addirittura tendere a eliminare – il controllo dei nuovi medicinali tramite i sacrifici di cavie animali. Infatti, oggi, si possono osservare direttamente in vitro le azioni che i cromosomi e i geni delle cellule umane compiono ininterrottamente da centinaia di milioni di anni, azioni aggiornate dalla selezione naturale. Tra i fenomeni osservabili vi è anche quello dell’apoptosi che sicuramente riveste un ruolo centrale nell’equilibrio dell’organismo vivente. Tale processo potrebbe essere definito da una formula che descriva il trattamento necessario per eliminare le parti dannose con mezzi informatici anziché biologici.

Ora si può anticipare che, in logica combinatoria, uno degli strumenti che saranno prossimamente definiti, il combinatore K (che appartiene alla base di detta logica), ha una funzione di killer.

È importante, prendendo lo spunto dall’apoptosi, ritornare a parlare della biologia e in particolare delle recenti proprietà curative del NGF (Nerve Growth Factor), fattore di crescita delle cellule nervose, per la cui scoperta Rita Levi-Montalcini è stata insignita nel 1986 del premio Nobel per la fisiologia o la medicina. L’analogia tra il fattore NGF (strumento biologico) e il funzionale (strumento logico) è che essi hanno la caratteristica comune di potersi applicare, quindi agire, su diversi oggetti, funzioni e perfino su sé stessi.

Non si deve però dimenticare che il principale mo­tivo della domanda iniziale era quello di dare il giusto peso al principale progresso scientifico che si è prodotto in questa prima decade del 21° sec., proprio grazie all’enorme sviluppo dei computer e dell’informatica (hardware e software), sviluppo tutto diretto alla soluzione di problemi, specialmente biologici, riguardanti l’umanità. Di seguito si cercherà di comprovare quanto affermato finora.

Useremo una fondamentale innovazione di questo secolo, Google, il più noto e potente motore di ricerca di informazioni, per effettuare la ricerca su un tema e per ottenere il numero totale dei risultati di tale ricerca. La lingua utilizzata è l’inglese. La tabella riporta i risultati di due diversi sondaggi: nel primo si ricerca l’occorrenza di un settore nell’ambito di una lista scientifica, nel secondo la ricerca è effettuata nell’ambito di una lista di impronta informatica.

Osservando la tabella si possono effettuare alcune considerazioni. Nella prima lista, logic ed engineering sono vocaboli con significati multisettoriali, quindi la loro alta occorrenza non deve stupire. Peraltro, i termini disciplinari, eccetto physics, sono tra loro confrontabili (psychology, biology, mathematics, chemistry).

Nella seconda lista sorprende l’occorrenza futuribile, anche se non eccezionale, di quantum computing. Sembra che l’interesse per l’Universo predomini su quello per la vita. Il resto della graduatoria sembra confermare la scelta di unificare il linguaggio umano con quello degli algoritmi.

È arrivato il momento di mostrare al lettore, per es., come ci si possa difendere contemporaneamente dai virus telematici e biologici.

Nel corso del 20° sec., alcuni studiosi si sono accorti che, per la descrizione dei processi biologici e di quelli informatici, ci si avvale essenzialmente delle stesse tre componenti: la comunicazione a distanza, l’aritmetica e la logica (queste ultime due in modo assai elementare). Ciò corrisponde esattamente alla descrizione di un algoritmo, cioè mette in atto l’espressione ‘unifichiamo il linguaggio umano con quello degli algoritmi’ proposta in precedenza.

Riassumendo, i concetti che finora si è cercato di mettere in evidenza sono: a) un tema informatico attuale mirante a un’evoluzione del software meno caotica, diretta verso un importante scopo scientifico, ossia chiarire e difendere l’evoluzione dell’umanità e del pianeta che ci ospita; b) la descrizione dell’essenza dei computer (basata ancora oggi sui trasferimenti del contenuto da una cella di memoria a un’altra e sulle operazioni aritmetiche necessarie per l’esecuzione dei suoi microprogrammi), come lo studio di metodi di risoluzione di opportune equazioni aventi un particolare carattere algebrico; c) le realizzazioni di Gödel che, malgrado le raccomandazioni diffuse dai logici matematici, non ha posto limiti alla risolubilità dei problemi che coinvolgono la logica matematica e l’aritmetica ma, al contrario, ha garantito la loro risolubilità in un tempo illimitato, grazie alla libera creatività concessa ai ricercatori.

Appare dunque chiaro come Gödel sia da considerare il più importante informatico teorico del 20° secolo.

Gli elementi stabili e la riscrittura

Per potere realizzare pienamente la finalità espressa nella risposta alla domanda dell’introduzione (quella di sfruttare la possibilità aperta da Gödel), dobbiamo superare un ostacolo che si è concretamente manifestato all’inizio del 21° secolo. Le persone che si dedicano alla produzione di software spesso non hanno un linguaggio sufficientemente aggiornato. Evidentemente, manca una distinzione fondamentale tra i concetti relativi agli strumenti usati da queste persone: linguaggi di partenza e di arrivo, traduttori, sistemi operativi, natura e forma dei dati e dei risultati. Ognuno di essi diventa, invece, una sorgente di complicazioni.

La distinzione che qui si propone è quella fra caducità e perennità. Gli oggetti relativi a tale distinzione possiamo chiamarli trasformabili e stabili. Elementi stabili sono: dati, risultati, o indirizzi di entrambi (tutti rappresentati da numeri interi) o (nomi di) programmi, operatori, operandi. L’idea principale che si vuole usare (si tratta pur sempre del significato che si vuole attribuire a frammenti informativi, cioè a un certo numero di bit) è che tale significato dipende esclusivamente dalla loro posizione relativa. Siamo arrivati, dunque, a descrivere ogni processo di calcolo mediante un numero finito di regole di trasformazione del tipo

→ ...

dove a sinistra della freccia troverà posto soltanto un oggetto trasformabile, mentre alla sua destra vi dovrà essere un oggetto o trasformabile o stabile.

Nel 1909 il matematico Axel Thue inventò un sistema di riscrittura con la precedente simbologia dove a sinistra e a destra della freccia si trovavano stringhe alfabetiche (costituenti un linguaggio la cui sintassi ne decideva l’appartenenza) come strumento per decidere problemi sulla risolubilità di semigruppi associati a tali stringhe, chiamato poi, in suo onore semi-Thue system.

Le strutture delle stringhe a sinistra della freccia, appartenenti a regole diverse, erano diverse fra loro, in modo tale che ogni stringa del linguaggio poteva soddisfare al più un solo primo membro di tali regole. Se ciò succedeva, la stringa veniva trasformata in quella del secondo membro di tale regola, altrimenti (cioè se la stringa non soddisfaceva alcun membro sinistro di tali regole) tale stringa costituiva un elemento stabile.

Alla ricerca dei combinatori stabili

Una conferma di quanto appena riferito ebbe luogo in una conferenza che il logico Moses I. Schönfinkel sostenne nel 1920, seguita da un articolo in cui fu definita la logica combinatoria (Über die Bausteine der mathematischen Logik, «Mathematische Annalen», 1924, 92, pp. 305-16). Da non dimenticare è anche il contributo importante che il logico Haskell B. Curry diede a tale disciplina nel periodo compreso tra il 1928 e il 1982 (anno della sua scomparsa).

Si vogliono ora illustrare i combinatori di Schönfinkel, insieme al relativo sistema di riscrittura, e caratterizzarne gli elementi stabili. Tuttavia, per usare le nozioni introdotte nel primo capitolo si deve tener conto delle nuove visioni sull’informatica che permettono di semplificare la cosiddetta sintassi guadagnando in semantica. Non è necessario usare soltanto una dimensione, cioè le stringhe che, per rendere sufficientemente espressive le formule, necessitano di un ausilio abbastanza noioso, le parentesi. Invece si guadagna nel rappresentare visivamente un’operazione, la cosiddetta applicazione (nel senso di applicare una funzione, o operatore, a uno o più argomenti) usando due dimensioni. Si utilizza qui un nome più umano, più personale e più limitato, doppia delega, ossia si delega un oggetto stabile, per es. di nome ‘a’, a essere un operatore, oppure a essere un operando a seconda della posizione indicata

a ^ oppure ^ a

(dove ovviamente non sono illustrate deleghe, ma soltanto semideleghe).

La logica combinatoria può essere generata dai due soli combinatori S e K, oggetti stabili, ripetutamente usati come operandi e operatori. Prima di continuare si vuole però illustrare come, disponendo soltanto di due tipi di deleghe, possiamo perfino ottenere che un operatore possa avere anche più di un operando e, addirittura, un numero finito qualsiasi di essi. Intanto si noti che se a e b sono due nomi di combinatori la notazione:

a ^ b

può stare solo a significare la simultanea delega di a come operatore e di b come operando. Quindi, la scrittura bidimensionale

^ c

a ^ b

significherà che l’operatore a possiede, ordinatamente, i due operandi b e c.

Per descrivere la logica combinatoria bastano due regole di riscrittura, che descrivono rispettivamente S e K come operatori usando, come preannunciato, alberi binari al posto di stringhe. Tutti i nodi saranno etichettati da S o da K quali unici generatori della logica combinatoria. Le radici saranno rappresentate dall’operatore delega ^ talvolta con @ sovrastante, ma solo come etichetta (superflua), mentre tutti gli altri vertici sono etichettati da S, K o, se si tratta di oggetti incogniti, da lettere (per es., a, b, c) che rappresentano combinazioni stabili indeterminate, i cui nodi apparterranno pur sempre all’insieme {S,K}

(S) (K)

^

^ c ^ ^

^ b → ^ ^ ^ b → a

S a a c b c K a

Ora trasformeremo questa riscrittura di alberi binari in quella su stringhe. Attenzione, però! A differenza delle abitudini (cominciare a leggere un albero dalla radice, in alto, verso le foglie in basso), qui si comincia a leggere dalla foglia, la più in basso a sinistra. Per es., se postscriviamo @ al posto dell’operazione ‘delega’, le riscritture delle regole (S) e (K) (da alberiformi a stringhe) diventeranno:

S a @ b @ c @ → a c @ b c @ @

K a @ b @ → a

Si osservi che il combinatore K è molto particolare. Si può dire che opera su a e b, ma il risultato finale è a. Esso appartiene dunque alla categoria dei selettori.

Le stringhe ottenute dalla lettura degli alberi, altro non sono che delle espressioni algebriche scritte in notazione polacca inversa che, abolendo le parentesi, si prestano ottimamente a essere eseguite da un elaboratore dotato di stack (pila). Si noti che questo risultato è stato raggiunto privilegiando la semantica rispetto alla sintassi.

Segue ora la determinazione di tutte le forme stabili derivanti dalle regole definitorie (S) e (K) nelle versioni alberi binari in cui, come al solito, a,b,c siano elementi dell’insieme {S,K}. Esaminiamo, perciò, le varie ipotesi: a) a=S. Dopo aver usato una volta la regola definitoria di S consegue che, per poterla applicare una seconda volta, a deve essere delegato almeno 3 volte mentre a disposizione ve ne sono soltanto 2, quindi il risultato è stabile. Usando a=S nella regola definitoria di K consegue che, qualunque sia b, il risultato è S quindi il risultato è stabile; b) a=K. Dopo aver usato una volta la regola definitoria di S consegue da quanto detto prima, cioè che si può applicare una sola volta la regola definitoria di K, si ottiene l’elemento stabile c.

Il λ-calcolo come macchina astratta

I combinatori che ci hanno interessato fino a questo momento sono entità stabili e, sebbene non dotati di spazio interno disponibile, sono collocabili su un piano e passibili di diversi comportamenti secondo il ruolo (attivo o passivo) cui sono stati delegati. Se un combinatore ha un ruolo passivo può essere: soppresso, spostato oppure raddoppiato dal combinatore investito del ruolo attivo. Se invece il ruolo del combinatore, appena nominato, è attivo, esso si comporta come un programma fisso e inalterabile.

I λ-termini stabili (cioè, tradizionalmente, chiusi e in forma normale) che si stanno per introdurre sono entità dotate di spazio interno sufficientemente ampliabile che, se riempito, ne può alterare le finalità, rendendo i loro comportamenti più simili a quelli dei sistemi operativi, comprendendo i loro microprogrammi, assumendo perfino un comportamento robotico. Infatti, mentre i combinatori (ne esistono molti altri oltre a S e K) hanno un nome costituito da una lettera maiuscola più o meno segnata, per es. I, B, B’, W, W*, C, C* ecc., i λ-termini non hanno bisogno di nomi; tuttavia, come si vedrà fra breve, la β-regola di riscrittura ne definisce il comportamento. Si è quindi in grado di confutare la convinzione che il λ-calcolo è troppo astratto, troppo lontano dalla realtà e dalle esigenze pragmatiche dei computer e dell’informatica applicata odierna. Già in un articolo di Giuseppe Jacopini (Macchina universale di von Neumann ad unico comando incondizionato, «Calcolo», 1965, 2, 1, pp. 23-29) – che tratta il trasferimento del contenuto da una cella a un’altra, cioè la comunicazione (le operazioni aritmetiche stavano nella gestione del contatore delle istruzioni) – si dimostra che gli attuali computer hanno una sola istruzione: un trasferimento d’informazione. Ebbene anche il λ-calcolo ha una sola operazione: quella che noi abbiamo chiamato delega. Come avviene il trasferimento dell’informazione? Semplicemente, precisando cosa dev’essere trasferito e dove. Il nome di questo operatore è sostituzione.

Finita la fase di benevola polemica tendente ad annullare i pregiudizi sul λ-calcolo, si rendono ora necessari esempi che confermino le giustificazioni addotte. Ecco i classici λ-termini che definiscono i combinatori S e K e le loro successive semplificazioni (nell’ordine, variabili con indici, soltanto con gli indici delle variabili o di de Bruijn, a grafo):

S=λxyz.xz(yz) K=λxy.x

S=λ123.13(23) K=λ12.1

S=123.13(23) K=12.1

Per rispetto alla tradizione, in questo saggio, si è rinunciato all’abolizione della lettera λ. Si riserva, invece, per la prossima sezione, la rappresentazione a grafo di S e K come λ-termini.

Si noti che l’albero di S come visto in (S) si ritrova nella definizione di S, più le frecce, che indicano i posti dove deve avvenire la sostituzione. Lo stesso fenomeno accade, anche se in modo molto più semplice, per K e così anche per ogni λ-termine stabile (fig. 1).

L’ultima osservazione è importante. Infatti dà la chiave per individuare l’unica regola di riscrittura, per noi, del λ-calcolo, chiamata β-regola, qui detta (doppia) delega.

In effetti, nella versione classica del λ-calcolo, esiste un’altra regola di riscrittura, chiamata α-regola, che consiste nel ridenominare tutte le variabili legate. Nel nostro caso i nomi delle variabili sono spariti poiché i luoghi di sostituzione sono imposti dalle frecce del grafo. Quindi a noi basta descrivere la seguente regola (unica) di riscrittura cui assegneremo il nome β (fig. 2).

Si noti che, nella figura 2, le frecce arrivano alla base del termine a sinistra della freccia orizzontale β perché tale termine, delegato come operatore, è scritto su una riga; il termine delegato come operando è troppo piccolo per vederne le frecce.

I risultati raggiunti e quelli da raggiungere si prestano alle seguenti considerazioni riassuntive.

Nella prima parte di questo saggio si è discusso sui vari atteggiamenti che si possono (o meglio si dovrebbero) assumere nei confronti dell’attuale informatica, cercando di capire i suoi vari intendimenti. Nella seconda parte si è cercato di descrivere, nel modo più uniforme possibile, i mezzi tecnici d’approccio alla soluzione di tutti gli interrogativi posti nella prima parte. Sembra giusto chiamare tale approccio programmazione funzionale.

Attenzione però! Se vogliamo unificare il nostro approccio (e in realtà a questo punto dobbiamo farlo), il vocabolo funzionale deve poter acquistare nuovi significati e incarichi: l’aggettivo funzionale può essere anche un sostantivo; come tale può indicare un numero intero, combinatore e (con tutti i suoi aggettivi) funzione (con argomenti e/o valori appartenenti a ciascuna delle categorie appena nominate); questa polisemantica acquisita da uno stesso vocabolo semplifica e aumenta enormemente il potere risolutivo degli oggetti finora introdotti rispetto ai problemi che ci siamo posti all’inizio di questo saggio.

Quanto appena detto si applica soprattutto a compiti accennati nella prima parte di questo saggio, nella quale si è considerato K come killer e sono stati affrontati problemi che descrivono fenomeni spiacevoli, quali il fuoco amico e altri pericoli da evitare, derivanti dal fatto che un funzionale si trova nella condizione di dovere operare su sé stesso.

La prima riflessione che occorre fare è la seguente: è sempre così pericoloso che un funzionale operi su sé stesso? Una risposta è data dall’illustre creatore del λ-calcolo Alonzo Church che, intorno alla fine degli anni Trenta del secolo scorso, introdusse i numerali di Church, i quali rappresentano i numeri naturali con λ-termini chiusi in forma normale. Se n rappresenta il numero naturale n, allora n^n rappresenterà la potenza n-esima di n (più precisamente n^m rappresenterà mn). La risposta alla precedente domanda è pertanto negativa. Data la sua importanza, riprenderemo fra poco il problema dell’operare su sé stessi, in quanto in grado di suggerire ulteriori verità nel campo scientifico proposto nel presente articolo.

Un’altra riflessione è la seguente: il fatto d’aver dato il nome di funzionale a ogni elemento stabile della logica combinatoria (generata da S e K ) può ovviamente essere esteso agli elementi stabili (le forme normali chiuse) del λ-calcolo e tutto ciò faciliterà il trattamento equazionale dei problemi annunciati nella prima parte di questo saggio.

Equazioni, dati e risultati: uno, due, molti

Ci avvaliamo della riflessione appena espressa: le equazioni verteranno su funzionali, alcuni noti, altri incogniti, comunque stabili. Il funzionale fondamentale è quello indicato con il simbolo ^, operante su due argomenti che abbiamo incontrato, prima fra i combinatori, poi fra i λ-termini. Ciò che ora ci deve interessare è la molteplicità degli oggetti stabili che prenderemo in considerazione; ve ne sono due specie, ambedue ordinate linearmente: una, in cui la molteplicità è nota, è chiamata n-pla; l’altra, invece, in cui la molteplicità può essere qualsiasi, purché finita, è chiamata lista.

Diamo la preferenza al funzionale n-pla, e in particolare a quello inventato da Church, detto appunto n-pla di Church (nCh), in quanto denso di significati nei due possibili ruoli cui può venire delegato: quello di operatore e quello di operando. Usando la notazione di de Bruijn, l’n-pla nCh dei funzionali f1,…, f_n sarà descritta da

nCh=1.1f1…f_n

Definiamo adesso un funzionale Uⁿ_i (selettore della i-esima componente di una nCh)

Uⁿ_i=12…n.i

(si tratta d’un operatore che applicato a n funzionali f1,…, f_n li cancella tutti tranne l’i-esimo f_i).

Come esempio, usando le definizioni e gli schemi precedenti vale la relazione:

®

nCh^Uⁿ_i → f_i

ovvero, scrivendo per esteso i -termini,

®

1.1f1…f_n^12…n.i → f_i

Nel 1974, l’autore di questo saggio e Mariangiola Dezani-Ciancaglini hanno dimostrato che ogni funzionale con una sola astrazione esterna D, chiamato deed, se applicato a un opportuno funzionale, può ottenere come risultato un funzionale arbitrario.

Uno alla volta… per carità

Il più semplice deed è ovviamente 1.1, cioè l’operatore che restituisce inalterato il suo operando, ma lo è anche un’n-pla di Church.

Risulta poi che ogni deed D possiede almeno un punto fisso F che a sua volta è un funzionale: D^F=F. Inoltre, usando quest’ultimo risultato, si dimostra che per ogni coppia di deed D1, D2 l’equazione D1x=D2x ha sempre almeno un funzionale come soluzione.

D’altra parte, utilizzando n-ple di Church e i suoi proiettori, è sempre possibile: a) trasformare ogni sistema costituito da h>1 equazioni coinvolgenti n funzionali dati M1,…, M_n in una sola equazione con soltanto due funzionali dati M′1, M′2: M′1x=M′2x (E. Engeler, The combinatory programme, 1995, p. 7); b) trasformare ogni funzionale M in un deed D; c) trasformare quindi la precedente equazione nella nuova equazione D′1x=D′2x.

Vale allora la seguente conclusione: si può risolvere ogni sistema di equazioni funzionali mediante i deed.

Vorremmo far notare, però, che mentre la trasformazione di un sistema di equazioni a una soltanto, con il metodo delle n-ple di Church e i proiettori, è rigorosamente reversibile, la trasformazione dei due M in due D non conserva (ma in senso ottimistico) la risolubilità delle rispettive equazioni. Se la prima delle due equazioni non è risolvibile, la seconda lo è sempre. Si riporta il seguente esempio:

Kx=Ox

ovvero (con i -termini)

(12.1)x=(12.2)x

Omettiamo qui una discussione filosofica che si connette inevitabilmente al contributo di Gödel o anche ai risultati dei fisici teorici che, per risolvere i loro problemi, sono ricorsi a più dimensioni, ben oltre la quarta (spazio-tempo) raggiungendo talvolta l’undicesima o anche infinite dimensioni (teoria dei quanta).

Si tenta qui di rispondere nel modo migliore alle domande poste nella prima parte di questo saggio, fornendo soluzioni ai problemi più critici posti, ossia sfruttamento dell’apoptosi (eliminazione delle cellule malate con strumenti informatici); sfruttamento del fattore NGF per bloccare lo sviluppo del morbo di Alzheimer ecc.; eliminazione dei virus informatici e biologici sopprimendo le azioni dirette di agenti su loro stessi (tra cui la riproduzione).

Per risolvere i problemi presenteremo un funzionale M, il più semplice possibile, che contiene le minacce citate e che spariranno trasformandolo in un particolare deed (deed ereditariamente finito, in breve def) illustrandone l’algoritmo.

Riassumiamo la nomenclatura e i risultati principali. Funzionale è un -termine chiuso in forma normale. Nelle equazioni, dati e incognite sono funzionali. Ogni sistema di n equazioni è riducibile (tramite l’uso di n-ple di Church e di proiettori, come visto in precedente) a una sola equazione del tipo

M1x=M2x

dove M1 e M2 sono funzionali noti, mentre x è quello incognito. L’equazione potrebbe non avere una soluzione esatta quando M2 è un sottotermine di M1 (essendone stato scelto, per convenzione iniziale, il numero di astrazioni iniziali minore o uguale a quello di M1).

Per aumentare l’efficienza dell’algoritmo di risoluzione è conveniente riuscire a trasformare M1 e M2 in deed ereditariamente finiti, defM1 e defM2.Un deed ereditariamente finito è un funzionale che possiede una sola astrazione esterna mentre le astrazioni interne possono essere presenti (altrimenti tale funzionale sarebbe semplicemente un’n-pla di Church) ma apparire soltanto una alla volta.

Vogliamo costruire DM, l’albero di Dezani (fig. 3) partendo dal funzionale M descritto come stringa del -calcolo. Tale stringa, in generale può contenere parentesi aperte e chiuse che verranno appunto eliminate in DM; però, rappresentando M un funzionale stabile, a nessuna sottostringa di esso si dovrà potere applicare la β-regola. Nella stringa che rappresenta M non si dovranno mai presentare le seguenti sottostringhe: ‘((’, ‘(un solo intero positivo)’. Infatti, una stringa rappresentante un funzionale non può iniziare con una parentesi aperta, o perché la corrispondente chiusa dovrebbe terminare il funzionale (e allora sarebbe inutile), oppure perché dovrebbe operare su ciò che segue perdendo la sua stabilità. Perciò ogni funzionale inizia con una stringa 12…n.i (che, se finisse lì, rappresenterebbe il selettore Uⁿ_i). In questo caso D Uⁿ_i=<n,i> e l’albero è una radice-foglia che coincide con la sua etichetta. Ora siamo in grado di descrivere come è strutturato l’albero DM per ogni funzionale M descritto come stringa. Abbiamo visto che la sua radice è etichettata dalla coppia <n,i>, che corrisponde al selettore Uⁿ_i. Si ha che ogni nodo dell’albero DM è etichettato da un selettore. Scegliamo come esempio un M di cui abbiamo anticipato i pregi:

123.3(4.3(5.4(6.65)))(111)

Scegliamo, da sinistra, coppie di numeri separati da un punto: per prima otteniamo <3,3> (l’etichetta della radice). Le due coppie di parentesi corrispondenti (aperta chiusa) che seguono 3 in M indicano che il nodo della radice ha due figli: il primo con etichetta <4,3> e il secondo con etichetta non ancora evidente, mentre è indiscutibile che <4,3> ha il figlio <5,4> e un nipote (figlio del figlio) <6,6>.

Continuiamo la ricerca di ciò che nella stringa può seguire immediatamente a destra dell’etichetta della radice: un numero non superiore a n che diventi in DM il primogenito della radice <n,i>; una parentesi aperta che segnali nell’albero DM la presenza di un nuovo figlio o di un nuovo fratello. Confermiamo che in tale stringa non si presentano due parentesi aperte consecutive perché ciò preannuncerebbe che N non è stabile e quindi non può essere un funzionale. Ogni funzionale co­mincia con il selettore 12...n.i, cui seguono numeri naturali, parentesi aperte e così via.

Ora bisogna effettuare la trasformazione della stringa rappresentante un funzionale M nell’albero binario DM i cui nodi siano etichettati da coppie di naturali positivi in ordine non crescente.

Ci rimane dunque solo di trovare le coppie in (111).

Osserviamo che (111) risulta essere il terzo figlio della radice <3,3>. Poiché, risalendo verso la radice dell’albero che ora stiamo costruendo, la prima astrazione che si incontra è 3 (non badiamo che in questo caso è anche l’unica), possiamo dunque scrivere al posto di (111):(<3,1>11). Lo stesso discorso si può ripetere per gli ultimi (potenziali) figli di <3,1>.

A questo punto, descriviamo la trasformazione da DM in D(defM). D(defM) avrà il numero doppio dei nodi di DM poiché, per generarlo, dovremo partire dall’albero DM, e a ogni nodo, come prima operazione, aggiungergli un figlio (in posizione primogenita, con etichetta uguale a quella del padre) che di­venta per tale motivo una foglia di D(defM). Dopo il raddoppiamento dei nodi con le rispettive etichette stabiliremo l’ordine di visita dei nodi di DM, che devono subire ovviamente un cambio di etichetta per diventare nodi di D(defM). Cominciamo dalla radice di DM. Dal momento che defM è (per definizione) un deed, <1,1> deve essere l’etichetta della radice di D(defM). Decidiamo a questo punto l’ordine in cui dobbiamo visitare i nodi di DM, dopo la radice, per trasformarli in nodi di D(defM).

Pensiamo a DM come se il suo albero dovesse costituire la parte solida del delta di un fiume allo sbocco nel mare. Si tratta di visitare uno dopo l’altro i ‘porti’ del delta, cioè i nodi dell’albero, e trasformarne l’etichetta circumnavigando il delta in senso antiorario, cioè partendo dalla ‘(’ e arrivando alla ‘)’ sua radice etichettata <1,1>.

Avendo preannunciato l’ordine di visita dei vari nodi di DM esaminiamone ora la trasformazione delle etichette (eccetto la radice e i nuovi primogeniti, già sistemati) per ottenere quelle di D(defM).

Cominciamo, dunque, con il calcolare la nuova prima componente dell’etichetta del nodo in esame. Confrontiamone la corrispondente vecchia (ora già nella foglia del nuovo primogenito di suo padre) con l’attuale prima componente del padre. Soltanto se il primo dei due numeri supera il secondo allora la nuova prima componente è quella del nodo padre incrementata di 1, altrimenti essa coincide con quella del padre. Confrontiamo ora la seconda (vecchia) componente (sempre nella foglia del nuovo primogenito di suo padre) con l’attuale seconda componente del padre. La nuova seconda componente viene ora calcolata in modo simmetrico alla prima. Tutto ciò viene ripetuto fino alla fine della circumnavigazione (fig. 4).

L’uso dei deed ereditariamente finiti (defM, dove M è un funzionale, per es. la soluzione di un’equazione funzionale) garantisce alcuni ulteriori importanti risultati: in primo luogo le autoapplicazioni che si possono trovare in M spariscono in defM. Ciò elimina le azioni distruttive che si possono presentare sia in un virus informatico sia in un funzionale che descrive il funzionamento di un virus biologico, permettendo inoltre di impiegare le tecniche, usate come difesa dai cultori della teoria dei tipi elementari. In secondo luogo, un defM, grazie all’intervento dei funzionali che fanno delle sostituzioni una per volta, può far risparmiare spazio e tempo nell’esecuzione di programmi, la cui complessità abbia carattere esponenziale, rendendola più simile a quelli la cui complessità ha carattere polinomiale. E infine, il software che utilizza i defM anziché gli M incoraggia la produzione di robot nanotecnologici, i quali potranno essere introdotti con maggiore facilità nell’organismo umano con la prospettiva di liberarlo dalle malattie operando di­rettamente sulle cellule malate.

Un’ipotesi avveniristica e impressionante riguarda la possibilità per i cellulari di potere abitare nel nostro corpo e trasmetterci, per es., film a carattere olografico, quindi a tre dimensioni, senza pellicola e senza schermo, obbedendo a istruzioni non trasmesse dalle nostre dita o dalla nostra voce, ma generate dalla nostra mente, dai nostri pensieri.