Elaborazione con risorse illimitate e infinito potenziale

Tutte le elaborazioni di informazioni sono riconducibili a trasformazioni e composizioni di stringhe: anche le elaborazioni decisionali si possono vedere come trasformazioni di alcune stringhe in una stringa risultato che fornisce un valore vero o falso, oppure un si o un no.

Tutte le elaborazioni, quale che sia la natura dell'operatore che le esegue (umano o artificiale) richiedono essenzialmente risorse di tre tipi: tempo di elaborazione, supporti di memoria ed istruzioni operative.

Ogni elaborazione procede per passi successivi che possono essere riferiti ad una scala dei tempi discreta convenzionale.

Nell'istante $t=0$ si ha la situazione iniziale, ovvero, come è preferibile dire, l'elaborazione si trova nella configurazione iniziale. Sui nastri di input sono registrati i dati iniziali e le relative testine sono posizionate in determinate posizioni iniziali; si deve inoltre pensare ad un agente umano o artificiale chiamato controllo che sta esaminando la prima delle istruzioni operative, comandi che esprimono le esigenze da soddisfare attraverso le elaborazioni previste ed in particolare attraverso la elaborazione attuale.

Quando si esegue un passo evolutivo, il controllo, sulla base della istruzione corrente (stringa che esprime l'esigenza operativa attuale) e delle informazioni trovate dalle testine di lettura invocate dall'istruzione nelle caselle sulle quali sono posizionate, decide

- se muovere alcune testine,

- se modificare i contenuti di alcune caselle dei nastri letti o di altri nastri ausiliari o di output,

- se passare ad altra istruzione.

È essenziale che le istruzioni siano interpretabili dal controllo senza ambiguità operative.

L'elaborazione procede in questo modo per passi successivi che conviene riferire agli istanti individuati dai valori di una variabile temporale convenzionale $t=0,\ t=1,\ t=2,...$.

Una elaborazione ben organizzata giunge ad arrestarsi in una certa configurazione finale soddisfacente per l'esigenza che l'ha motivata. Fondamentalmente si ha la conclusione di una costruzione con la individuazione di una stringa che esprime un oggetto richiesto; questa può configurarsi in particolare come determinazione di un numero o come risposta positiva o negativa ad una domanda a due vie.

Una elaborazione però si può anche concludere con l'arresto delle operazioni per aver trovato una situazione anomala, cioè non prevista, che non consente di giungere ad una stringa risultato interpretabile; in questo caso si parla di conclusione erronea.

Inoltre, come vedremo meglio più avanti, può accadere che l'elaborazione non giunga ad una conclusione.

Conoscere una elaborazione consiste nel sapere quello che si riscontra nelle successive configurazioni e avere chiaro ogni passaggio da una configurazione alla successiva sulla base delle informazioni e della istruzione correnti.

Osserviamo che la schematizzazione data delle elaborazioni non pretende di dare una rigorosa giustificazione di una loro validità: essa si limita ad invocare per le elaborazioni che si utilizzano nella esposizione la ragionevole riproducibilità delle manovre richieste dalle istruzioni e della evoluzione complessiva e conseguentemente la riproducibilità delle costruzioni.

Per la descrizione di una elaborazione non occorre analizzare i dettagli dei processi mentali o materiali che portano ad ogni nuova configurazione: basta che sia garantito che essi rispettino l'istruzione corrente.

Dall'esigenza di riproducibilità segue l'esigenza di essere in grado di descrivere senza ambiguità l'evoluzione di una elaborazione e quindi l'esigenza di disporre di un modello discreto: ogni elaborazione procede con azioni discrete esprimibili con interpretazioni di stringhe istruzioni e trasformazioni di stringhe dati, azioni riferibili a successivi passi discreti riferibili a una sequenza (o successione) di istanti discreti.

Perché ogni esecuzione sia effettivamente realizzabile, deve essere sviluppata su nastri finiti, attraverso un numero finito di passi e deve essere retta da un complesso di istruzioni, che devono essere espresse finitamente e senza ambiguità di interpretazione.

Poniamo poi l'esigenza di occuparsi di procedimenti di ampia portata: in caso contrario non si fa matematica, informatica, scienza o tecnologia e non si producono enunciazioni scientifiche o tecnologiche, ma ci si limita a dare risposte ad hoc ad esigenze episodiche. Dicendo questo non si vuole fare sfoggio di snobismo scientifico-tecnologico denigrando le attività mosse da esigenze episodiche: si vuole solo evidenziare che le attività scientifiche e tecnologiche si pongono il fine di dare indicazioni conoscitive e operative dotate di ampia potenziale utilizzabilità.

All'esigenza dell'ampia portata si collegano tre richieste programmatiche per le elaborazioni:

1. occorre essere in grado di operare con stringhe di lunghezza arbitraria: questo richiede nastri estendibili quanto si vuole
2. occorre essere in grado di far procedere le elaborazioni quanto serve: per costruire stringhe molto lunghe, ovviamente, servono tempi molto lunghi
3. occorre avere la possibilità di richiedere manovre molto elaborate, cioè; rette da complessi di istruzioni estesi ed elaborati quanto serve.

Le apparecchiature informatiche attuali consentono prestazioni molto elevate fornendo ampie memorie per dati e programmi estesi e alte velocità di elaborazione, cioè consentono esecuzioni formate da molti miliardi di passi. Inoltre la possibilità di far operare molte migliaia di elaboratori efficientemente collegati consente, in linea programmatica, una enorme estendibilità delle prestazioni.

Occorre comunque ribadire quella che può considerarsi una ovvietà: ad ogni istante si utilizzano risorse finite ed i risultati forniti da una elaborazione, utilizzabili per altre elaborazioni, possono essere ottenute solo dopo un numero finito di passi.

Sul piano espositivo, risulta però opportuno ricorrere ampiamente al termine infinito nella sua accezione di infinito potenziale. Si fa quindi riferimento ad entità che dovrebbero essere state prodotte su nastri infiniti da procedure che hanno operato attraverso una successione infinita di passi e quindi consumando risorse infinite.

In termini realistici si dovrebbe invece parlare di procedure che sono in grado di generare sequenze lunghe quanto si vuole, su nastri estesi quanto serve, procedendo attraverso un numero di passi elevato quanto è necessario. Di una tale procedura si può dire che produce sequenze illimitate di stringhe, registrandole su nastri illimitati, operando attraverso una successione illimitata di passi.

Descriviamo in particolare una procedura che genera le scritture unadiche di (tutti i) naturali ed una che genera (tutte) le stringhe sopra l'alfabeto $\{a,\ b,\ c\}$.

Entrambe operano per fasi successive, in ciascuna delle quali accodano su un nastro illimitato una nuova stringa.

La prima, dopo aver emesso le rappresentazioni unadiche di un certo numero $n$ di numeri naturali opportunamente separati da un segno separatore «,», presenta all'inizio del nastro una stringa come la seguente relativa al caso $n=6$:

, |, ||, |||, ||||, |||||,

Nella fase successiva essa riproduce nelle successive posizioni del nastro i caratteri compresi fra le ultime due occorrenze del separatore «,» ed accoda |, ottenendo

, |, ||, |||, ||||, |||||, ||||||,

cioè le rappresentazioni di un numero $n+1$ di naturali.

Le fasi della procedura per la generazione delle stringhe su $\{a,\ b,\ c\}$ sono più diversificate.

Per descriverla occorre pensare l'alfabeto ordinato, $\{a\ <\ b\ <\ c\}$ e ricordare due manovre: quella che effettua il confronto lessicografico fra due stringhe della stessa lunghezza e quella che trasforma una stringa in quella della stessa lunghezza immediatamente successiva secondo l'ordine lessicografico.

Le stringhe vengono generate per lotti relativi alle successive lunghezze e tra le stringhe della stessa lunghezza vengono generate prima le precedenti secondo l'ordine lessicografico.

Supponiamo che dopo una certa fase sul nastro si trovi la sequenza di stringhe (iniziante con la stringa muta):

$,\ a,\ b,\ c,\ aa,\ ab,\ ac,\ ba,\ bb,\ bc,\ ca,\ cb,\ cc,\ aaa,\ aab,\$

Nella fase successiva si trasforma la $aab$ nella successiva in ordine lessicografico e di lunghezza 3, cioè nella $aac$; quindi questa si accoda al nastro seguita dal separatore ottenendo:

$,\ a,\ b,\ c,\ aa,\ ab,\ ac,\ ba,\ bb,\ bc,\ ca,\ cb,\ cc,\ aaa,\ aab,\ aac,\$

Si procede con fasi simili fino ad avere sul nastro la sequenza di stringhe che si conclude con l'ultima della lunghezza 3:

$,\ a,\ b,\ c,\ aa,\ ab,\ ac,\ ba,\ bb,\ bc,\ ca,\ cb,\ cc,\ aaa,\ ...,\ ccb,\ ccc,\$.

In questo caso l'ultima stringa viene fatta seguire dalla $aaaa$, prima delle stringhe la cui lunghezza supera di 1 quella della precedente. In generale alla stringa $c^{s}$ si fa seguire la $a^{s+1}$.

Si possono poi descrivere procedure che generano insiemi di numeri ed insiemi di stringhe ottenuti restringendo i precedenti attraverso meccanismi selettivi che accertano se sono soddisfatte determinate richieste: in tal modo si ottengono, ad es., la sequenza illimitata da numeri primi o quella delle stringhe su $a,\ b$ aventi almeno una $a$ e un numero maggiore di caratteri $b$:

$2,3,5,7,11,13,17,...$

$,\ abb,\ bab,\ bba,\ abbb,\ babb,\ bbab,\ bbba,\ aabbb,\ ababb,\ abbab,\ abbba,\ baabb,\ ...$

Molte altre sequenze di parole e molti altri insiemi di questo genere si ottengono con una certa facilità mediante procedure che procedono a generare sequenze illimitate fondamentali, come quelle dei numeri interi e delle stringhe su un dato alfabeto, e che, richiamando un opportuno meccanismo, trasformano ogni nuova stringa in una sua corrispondente. In tal modo si ottengono semplicemente, ad es., la sequenza illimitata dei cubi dei successivi positivi e quella delle stringhe della forma $a^{n}b^{2n}$

$1,8,27,64,125,216,343,...$

$abb,\ aabbbb,\ aaabbbbbb,\ aaaabbbbbbbb,\ ...$.

Molto spesso è utile fare riferimento a queste sequenze illimitate. Dal punto di vista dello stretto realismo si dovrebbe dire che si utilizzano sequenze sufficientemente estese per effettuare verifiche di comparsa o per ricavarne stringhe opportune, tipicamente la stringa nella posizione determinata da un intero $n$ dato.

La disponibilità di una sequenza sufficiente a soddisfare le richieste conoscitive o elaborative si può accettare in linea di principio quando la procedura che consente di generarla è ben definita tanto che vi sia pieno accordo sulla possibilità di invocarla per ottenere nuovi risultati. In certi casi concreti può però accadere che per ottenere certi dati si richiedano risorse, soprattutto temporali, enormemente elevate: la concreta disponibilità di stringhe di posizioni elevate di nastri illimitati è quindi sottoposta a verifiche attuali.

Risulta molto conveniente di introdurre i termini parole infinite ed insiemi numerabili per individuare entità prodotte da procedure che sono in grado di operare a lungo quanto si vuole.

Si dice in breve che una tale procedura può proseguire all'infinito nella sua elaborazione.

In questo modo si è effettuata una astrazione attualizzante e servendosi della nozione di infinito potenziale, si possono introdurre notazioni e termini molto comodi per stringhe infinite e insiemi numerabili.

Insiemi numerabili particolarmente importanti sono: l'insieme che si denota ${\mathcal {A}}^{*}$ formato da tutte le stringhe su un alfabeto ${\mathcal {A}}$; l'insieme di tutti i numeri positivi denotato $\mathbb {P}$ e l'insieme di tutti i numeri naturali $\mathbb {N}$.

Vedremo che per trattare matematicamente vari altri insiemi numerabili conviene individuarli con notazioni opportune, come abbiamo appena fatto introducendo i simboli ${\mathcal {A}}^{*}$,$\mathbb {P}$ ed $\mathbb {N}$.

Si possono poi introdurre la relazione di appartenenza di un elemento ad un insieme numerabile, le operazioni su insiemi come intersezione, unione, eliminazione, differenza simmetrica, complementazione, le relazioni di sottoinsieme in senso lato e in senso stretto, la costruzione dell'insieme delle parti, le particolarizzazioni riguardanti funzioni, relazioni d'ordine ed equivalenze, le partizioni etc. .

Altre sequenze interessanti si ottengono con procedimenti che procedono in fasi nelle quali si costruisce una nuova componente a partire dalle precedenti (una, due, ..., o tutte)).

In tal modo si costruiscono, ad es., la sequenza dei numeri di Fibonacci ponendo $F_{0}=1$, $F_{1}=1$ e calcolando i successivi $F_{n}=F_{n-1}+F_{n-2}$ per $n=2,3,...$ .

Vedremo più avanti altri procedimenti che consentono di costruire insiemi che risulta più naturale presentare in due dimensioni (come quelle che conducono ai numeri negativi, ai razionali e ai coefficienti binomiali), sopra arborescenze infinite o sopra digrafi graduati infiniti.

Queste nozioni, come vedremo anche nel seguito, si possono introdurre in modo da giustificare l'applicazione dei procedimenti logico-deduttivi ad insiemi non finiti e non numerabili, solo attraverso una rigorosa impostazione assiomatica della teoria degli insiemi.

Valutando molto impegnativa la comprensione di una trattazione assiomatica completa, qui ci limitiamo a procedere costruttivamente con l'obiettivo di rendere plausibili le costruzioni che proponiamo anche quando si fa ricorso alla semplice intuizione.

Osserviamo che mentre è risultato agevole introdurre genericamente le operazioni e le relazioni riguardanti insiemi numerabili, si possono invece incontrare difficoltà quando si vuole affermare la possibilità di eseguire effettivamente certe operazioni e di verificare effettivamente certe relazioni.

La realizzabilità effettiva, nelle situazioni particolari delle costruzioni impostate in un'esposizione astratta, richiede di essere verificata in relazione alle circostanze.

Si osserva che molti risultati forniti dalle manovre sulle stringhe che andiamo esponendo si possono ottenere in più modi; due manovre che forniscono la stessa prestazione sono dette manovre equivalenti.

Molte circostanze richiedono di confrontare due manovre equivalenti per stabilire quale sia preferibile. Talora accade che la valutazione della manovra preferibile può essere riferita ad esigenze diverse e divergenti.

In molte circostanze risulta preferibile la manovra che permette di ottenere i risultati con un numero minore di passi. In altri casi interessa stabilire quale manovra richiede meno memorie (meno caselle sui nastri). In altri ancora conviene preferire la manovra che si sviluppa secondo modalità più semplici.