Definizione costruttiva di insieme numerabile

Gli insiemi espliciti presentano il vantaggio di introdurre costruzioni effettive che consentono di trattare concretamente numerosi problemi pratici. Per le applicazioni, ed in particolare per le elaborazioni dei dati, in definitiva servono solo entità effettivamente costruibili. Questo potrebbe indurre a pensare che le attività computazionali possano studiarsi senza far ricorso a nozioni che vadano oltre le suddette entità. In realtà, come la storia insegna, per riuscire ad affrontare molti problemi discreti e per individuare metodi di calcolo effettivo di portata ampia è indispensabile estendere in modo sostanziale la gamma delle entità matematiche trattabili e di far uso di nozioni che si collocano al di là di quelle effettivamente costruibili.

Innanzi tutto risulta molto opportuno, nella pratica espositiva, potersi servire di entità non riconducibili ad elenchi espliciti come l'insieme di «tutti» gli interi positivi, l'insieme di «tutte» le stringhe su un dato alfabeto ${\mathcal {A}}$ o come l'insieme di «tutte» le relazioni fra interi naturali, anche se evidentemente è insensato pensare di avere effettivamente registrata la totalità dei naturali, la totalità delle stringhe su ${\mathcal {A}}$ o la totalità delle relazioni che li riguardano.

Per proseguire si fa riferimento a meccanismi concretamente realizzabili che chiameremo procedure ; esse si vogliono in grado di effettuare operazioni su segni e stringhe che in linea di principio siano perfettamente riproducibili, procedendo per passi successivi completamente determinati da istruzioni riguardanti operazioni semplici, chiaramente formulate, espresse finitamente e coinvolgenti dispositivi di memoria per le stringhe che vanno elaborando; in particolare esse possono disporre di nastri dai quali attingere eventuali dati di ingresso, di nastri atti a fornire risultati delle loro elaborazioni e di nastri sui quali registrare dati temporanei costruiti durante le elaborazioni.

Oltre alle regole che definiscono una procedura, anche le configurazioni che essa assume durante le sue evoluzioni devono potersi esprimere in termini finiti, cioè mediante stringhe finite che ne descrivono senza ambiguità la situazione interna e che costituiscono i contenuti delle memorie (corrispondenti ai dati che elaborano). In particolare si fa riferimento ad una informazione chiamata stato assunto dalla procedura e che può assumere un insieme finito di valori $s_{1}$, $s_{2}$, ... ,$s_{sgm}$; quando l'informazione variabile assume il valore $s_{i}$ si dice che la procedura si trova nello stato $s_{i}$.

Si ammette anche che una procedura, quando necessario, possa disporre di tempi di elaborazione e di dispositivi di memoria estesi quanto si vuole. Per evitare che questa richiesta sia in conflitto con quella di effettiva realizzabilità dei meccanismi, occorre parlare di dispositivi di memoria ampliabili quanto può essere necessario, in modo che la procedura possa prolungare una sua evoluzione quanto serve e occorre dire che essa possa emettere risultati costituiti da stringhe lunghe quanto richiesto dalle circostanze. A questo proposito parliamo di evoluzioni e di dispositivi di memoria illimitati , aggettivo con il quale intendiamo abbreviare la qualifica «illimitatamente estendibili». Spesso si usa anche il termine «infinito», ad es. si parla di «macchine infinite». Assumendo un atteggiamento antiplatonico riteniamo che il termine «infinito» vada usato con una certa cautela.

Le procedure finalizzate alla emissione di un nastro di risultati, limitato o illimitato, si dicono procedure elencative ; il nastro emesso da una tale procedura va visto come elenco , cioè come stringa nella quale si individuano successivi identificatori. Eventualmente si ha un elenco illimitato costituito da identificatori di forma opportuna ed il cui numero può essere grande quanto si vuole.

Spesso invece interessano procedure che elaborano determinate stringhe immesse in un nastro di ingresso per trasformarle in corrispondenti stringhe presentate su di un nastro di uscita; queste vengono chiamate trasduttori . Si possono definire trasduttori che elaborano stringhe di ingresso illimitate e forniscono stringhe di uscita illimitate.

Si dicono accettatori le procedure che in seguito alle diverse evoluzioni possono emettere solo due segni, ad es. ${\mbox{t}}$ e ${\mbox{f}}$ (per true e false), oppure Y ed N (per yes e no), oppure 1 e 0. Queste procedure consentono di distinguere, tra le stringhe che possono essere sottoposte al loro esame, quelle che comportano l'emissione del segno ${\mbox{t}}$ (o Y, o 1) e le rimanenti che comportano l'emissione del segno ${\mbox{f}}$ (o N, o 0). Le prime vengono dette stringhe accettate dal meccanismo, le seconde stringhe rifiutate .

Per studiare in modo completamente soddisfacente le procedure occorrerebbe precisare come esse possono essere costruite. In effetti esse possono essere definite secondo svariati modelli, alcuni, piuttosto astratti, collegati a funzioni a valori interi, altri a procedimenti simbolici, altri a meccanismi formali; è importante rilevare che tutte queste impostazioni si dimostrano sostanzialmente equivalenti. In particolare nell'ambito della teoria dei linguaggi formali si può sviluppare lo studio delle cosiddette macchine di Turing e di queste si possono avere numerose varianti, dalle più essenziali dotate di pochi tipi di dispositivi, alle più articolate che giungono ad assomigliare a computers programmabili con un linguaggio di programmazione di ampia portata e dotabili di dispositivi di memoria illimitatamente estendibili. A questo proposito osserviamo che oggi un computer collegato in Internet può agevolmente accedere, tramite opportuno software di rete, ad un insieme praticamente illimitato di dischi e che questi possono considerarsi nastri bidimensionali, ovvero equivalenti ad estese porzioni di nastro.

Lo studio delle macchine di Turing o di un altro modello delle procedure, però, richiede di definire e sviluppare numerose nozioni piuttosto specialistiche. Qui preferiamo procedere con minore completezza al fine di giungere più speditamente a disporre di nozioni e notazioni riguardanti insiemi, relazioni e funzioni dotate di vasta portata ed utilizzabili per varie finalità.

Procederemo quindi a fornire esempi di procedure piuttosto semplici o comunque tali per cui risulti ragionevole confidare nella possibilità di descriverne costituzione e comportamento in termini privi di indefinitezze e quindi di avere a che fare con procedure perfettamente riproducibili.

Questo procedere «sulla fiducia» risulta delicato soprattutto per le procedure in grado di emettere elenchi illimitati, in quanto ogni elenco finito può essere sottoposto a verifiche mediante procedimenti finiti. Ci proponiamo quindi di studiare procedure elencative che consentono di introdurre entità che si possano considerare «insiemi» ma che non siano riconducibili a quelli espliciti e che ci permettono di ampliare rapidamente gli strumenti dimostrativi e computazionali a nostra disposizione.

Prima di procedere, osserviamo che ci si può rendere conto senza gravi difficoltà che si riesce a trovare un buon accordo su cosa si può lecitamente considerare procedura; inoltre si riescono ad individuare procedure che consentono di automatizzare gli svariati procedimenti di calcolo che sono stati messi a punto nel corso dello sviluppo delle discipline quantitative più consolidate a partire dalla matematica e dalla fisica.

Per contro l'introduzione «programmatica» di procedura sulla quale ci basiamo lascia aperte molte possibilità. Cerchiamo di individuare i vari tipi di evoluzioni che si possono avere per le procedure elencative.

Innanzi tutto si distinguono le evoluzioni limitate le quali si concludono dopo un numero finito di passi, cioè subiscono un arresto dopo aver emesso un elenco esplicito, e le evoluzioni illimitate, che «non si arrestano mai», cioè che sono in grado di compiere tanti passi evolutivi quanti si vogliono.

Queste ultime nel caso più favorevole e proficuo emettono elenchi illimitati privi di ripetizioni e costituiti da identificatori che seguono un ordinamento totale verificabile: più precisamente per un elenco di questo tipo, dati due qualsiasi identificatori diversi che compaiono in esso, si riesce a stabilire quale dei due compare prima dell'altro.

Con altre evoluzioni illimitate vengono emessi anche illimitati che presentano ripetizioni.

Veniamo ora a procedure che consentono di emettere elenchi illimitati facilmente controllabili. Innanzi tutto non è difficile immaginare meccanismi in grado di procedere ad emettere sopra un opportuno nastro le stringhe formate dai caratteri di un dato alfabeto oppure, meno genericamente, le scritture unadiche, binarie o decimali dei successivi numeri naturali.

Soffermiamoci su una procedura in grado di elencare numeri naturali, denotiamola $P\left(\mathbb {N} \right)$ e denotiamo con $E\left(\mathbb {N} \right)$ l'elenco illimitato del quale esso può generare una parte iniziale estesa quanto si vuole.

Con questo meccanismo quindi si possono controllare insiemi di naturali estesi quanto si vuole. Volendo rimanere solo nell'ambito delle entità effettivamente esplicitabili, si potrebbero presentare le proprietà dei naturali (e successivamente quelle degli interi, dei numeri razionali etc.) facendo riferimento ad insiemi finiti ampliabili a richiesta.

Seguendo questo atteggiamento purista, però, si avrebbero discorsi estremamente pesanti. Risulta molto più conveniente esprimersi facendo riferimento all'esistenza di una entità a se stante, chiamata insieme di tutti i numeri naturali, indicarla con il simbolo specifico $\mathbb {N}$ e scrivere $n\in \mathbb {N}$ per dire che un identificatore individuato dal simbolo $n$ denota un intero naturale.

La scrittura precedente si può leggere «$n$ appartiene all'insieme $\mathbb {N}$». Essa si può considerare una espressione opportunamente abbreviata della seguente: «fissato un naturale arbitrario $n$, la procedura elencativa $P\left(\mathbb {N} \right)$, se dispone di memoria sufficiente e se può operare a lungo quanto serve, può procedere fino ad emettere l'identificatore che esprime $n$».

La «totalità dei numeri naturali» invocata per dare un nome ad $\mathbb {N}$, anche se in conflitto con la pretesa di trattare solo entità formali effettivamente costruibili, può essere tranquillamente accettata come accorgimento verbale.

È opportuno usare il termine «insieme» per $\mathbb {N}$ e per altre entità individuate mediante procedure elencative, in quanto, come avremo modo di vedere, per esse si possono considerare gran parte delle nozioni viste per gli insiemi espliciti. Perdono senso solo le nozioni legate alla finitezza di questi ultimi.

In generale diciamo insieme ricorsivamente enumerabile una entità $S$ individuata esplicitamente da una procedura elencativa $P_{S}$ e dal relativo elenco potenziale $E_{S}$; si dice anche che gli identificatori che compaiono in $E_{S}$ rappresentano gli elementi che appartengono ad $S$. Per esprimere il fatto che $x$ denota un elemento di $S$ si scrive $x\in S$.

Questa definizione non esclude che $F_{S}$ presenti identificatori ripetuti; si può avere anche una procedura $P_{S}$ che emette stringhe che vengono replicate illimitatamente; in particolare si può incontrare una procedura che elenca solo un numero finito di tipi di stringhe ripetendone illimitatamente uno o più tipi.

Diciamo più precisamente insieme numerabile un insieme ricorsivamente enumerabile che viene individuato da una procedura elencativa che genera un elenco non ripetitivo illimitato.

Un insieme numerabile è quindi un cosiddetto insieme infinito , cioè un insieme che non è riconducibile ad un elenco esplicito e quindi finito.

La nozione di infinito introdotta con gli insiemi numerabili evidentemente riguarda un infinito potenziale.

Ricordiamo la distinzione fatta tra insiemi espliciti ed insiemi finiti : questi sono definiti come insiemi che si dimostra possibile esprimere mediante elenchi espliciti; ad un certo stadio delle conoscenze di un tale insieme potrebbe non essere noto un elenco che lo esprima. Un esempio si può trovare nell'insieme dei divisori di un intero positivo fornito da una scrittura di mille cifre: per ottenere i suoi divisori potrebbero rendersi necessarie elaborazioni estremamente onerose per le quali pensando di cominciare oggi ad utilizzare uno dei computers attualmente più potenti, si dovrebbero preventivare durate di molti millenni.

Ogni insieme ricorsivamente enumerabile può essere individuato da diverse procedure elencative. Tra queste se ne può trovare una non ripetitiva. In caso contrario, di fronte ad una procedura $P$ che si dimostra o si sospetta essere ripetitiva se ne può costruire una $P'$ equivalente non ripetitiva: si tratta di ampliare la $P$ con un meccanismo che controlla se ogni nuovo identificatore di elemento generato coincide o meno con un identificatore già emesso e nel primo caso evita di emetterlo.

Osserviamo che la nuova procedura non ripetitiva $P'$ risulta più complicata della $P$ e potrebbe essere molto meno efficiente. Quindi le procedure ripetitive di concezione semplice possono presentare interesse.

Disponendo di una procedura elencativa non ripetitiva si possono riscontrare diversi comportamenti.

1. Si dimostra che genera un elenco illimitato di elementi: in tal caso si individua un insieme numerabile.
2. Si dimostra che genera un elenco limitato di elementi. Si possono allora incontrare due comportamenti: (2a) si individua un elenco esplicito di elementi; (2b) con le risorse impiegate non si riesce a determinare effettivamente l'elenco esplicito completo degli elementi.
3. Non si riesce a decidere se l'elenco che la procedura va generando sarà illimitato o meno e con le risorse impiegate fino a un certo punto si dispone di un elenco parziale di elementi.
   

Idealmente si distinguono le procedure elencative (eventualmente non ripetitive) in grado di generare elenchi illimitati da quelle in grado di generare elenchi finiti. Volendo limitarsi alle informazioni che possono essere effettivamente acquisite, si deve invece tenere presente la possibilità di una procedura elencativa $P$ che, dopo l'eventuale generazione di un certo numero finito di identificatori, proseguendo nella sua evoluzione per un certo numero di passi non effettua alcuna emissione. In tale circostanza chi attende di conoscere la sua emissione viene lasciato nel dubbio sul comportamento della procedura:

(i)   dopo una ulteriore attesa la $P$ emetterà altri identificatori e si arresterà;

(ii)   si avrà il chiarimento del fatto che la procedura procederà ad una emissione illimitata che porterà ad un insieme finito (2a) o numerabile (2b);

(iii)   essa continuerà a comportarsi in modo che non si sappiano prevedere gli sviluppi successivi.

Diciamo insieme contabile un insieme ricorsivamente enumerabile che si rivela essere finito o numerabile. Solo le procedure per le quali si trovano i comportamenti precedentemente individuati da 1. e 2. individuano insiemi che si possono considerare contabili.

Diciamo invece insieme discreto un insieme che si trova essere finito o numerabile: in termini colloquali questo insieme si può qualificare come insieme che in linea di principio è ben controllabile.

Le distinzioni precedenti non si possono considerare mere sottigliezze senza conseguenze. In effetti si dimostra che risulta impossibile fare nette distinzioni fra le procedure elencative, quando queste vengono considerate nella loro globalità. Più precisamente si dimostra impossibile costruire un meccanismo o definire una procedura che consenta di stabilire la classe di comportamento alla quale appartiene una generica procedura elencativa. Questo è un risultato che pone dei limiti molto seri alla portata dei metodi computazionali e della matematica e dovrebbe essere sempre tenuto ben presente.