Insieme numerabile, definizione costruttiva

Da Wikipedia, l'enciclopedia libera.

Questa voce riguardante un argomento di informatica necessita di essere "wikificata", ovvero formattata secondo gli standard di Wikipedia (vedi l'elenco delle voci da wikificare). Modifica questa voce (anche se non sei esperto di informatica) seguendo le linee guida di Wikipedia e poi rimuovi questo avviso. (voce segnalata nel mese di maggio 2006) Vedi anche: Progetto informatica Portale informatica

Indice

1 Basta l'ambito finito per le elaborazioni nel finito?
2 Organizzazione delle conoscenze computazionali mediante insiemi non finiti
3 Procedure illimitate
4 Procedure elencative illimitate
5 Voci correlate

[modifica] Basta l'ambito finito per le elaborazioni nel finito?

Gli insiemi espliciti, cioè gli insiemi finiti che possono essere individuati mediante qualche elenco dei loro elementi, consentono di affrontare una grande varietà di problemi computazionali o di elaborazione di dati che nascono da esigenze pratiche specifiche; in particolare questo accade nell'ambito delle attività gestionali e amministrative.

Molti problemi concernenti insiemi finiti nati dalla pratica possono essere definiti e risolti senza ricorrere a nozioni matematiche complesse. Viceversa queste sono indispensabili, naturalmente, per affrontare problemi che richiedono modelli fisico-matematici e modelli probabilistici nel continuo.

Accade però che, anche limitandosi ad affrontare problemi concernenti insiemi finiti, la loro soluzione impone che si mettano a punto preliminarmente meccanismi che richiedono di precisare nozioni matematiche impegnative (ad es. nozioni afferenti alla teoria dei grafi, alla teoria dei linguaggi formali e alla teoria dei numeri).

Con lo sviluppo dell'elaborazione automatica dei dati si è avuta una forte crescita delle elaborazioni sugli insiemi espliciti e gran parte delle attività di programmazione riguardano gli insiemi espliciti. In particolare si può ricordare la attuale grande importanza delle elaborazioni collegate alle basi di dati.

Le moltissime persone che si occupano di elaborazione di dati possono essere indotte a pensare che per gran parte delle applicazioni sono sufficienti le conoscenze concernenti solo entità effettivamente costruibili, e quindi limitarsi alla conoscenza dei soli insiemi finiti e delle sole strutture finite. In particolare a questo convincimento possono contribuire le considerazioni che, correttamente, descrivono le elaborazioni dei dati come attività effettuate da strumenti finiti, in grado di trattare solo quantità determinate con precisione finita e registrabili in supporti di memoria finiti; inoltre si deve osservare che solo le elaborazioni di durata finita forniscono risultati effettivamente utilizzabili.

Vi sono quindi forti tendenze verso il convincimento che le attività computazionali che non necessitano di modelli fisico-matematici e probabilistici si possano affrontare senza far ricorso a nozioni che vadano oltre gli insiemi e le strutture finite.

In realtà, come insegna il passato (e in particolare molti capitoli della storia della matematica), 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 la cui conoscenza va presa in considerazione e servirsi, sul piano dell'organizzazione delle conoscenze e sul piano dell'orientamento delle concrete attività computazionali, di nozioni che si collocano al di là di quelle concernenti gli oggetti effettivamente costruibili che sono i soli attori nei calcoli effettivi.

[modifica] Organizzazione delle conoscenze computazionali mediante insiemi non finiti

I risultati delle attività computazionali per problemi riguardanti insiemi finiti espliciti costituiscono un complesso di conoscenze estremamente esteso e articolato che richiede di essere organizzato secondo criteri che vanno precisati con grande cura.

Innanzi tutto è necessario preoccuparsi di collegare risultati a prima vista diversi, ma che si possono ricondurre a enunciati unitari più astratti. Si devono quindi trovare elementi comuni in problemi di diversa formulazione; questi collegamenti vengono espressi mediante corrispondenze biunivoche, isomorfismi fra strutture della stessa composizione o attraverso criptomorfismi tra strutture di commposizione differente. Quando si sono chiariti collegamenti di questa natura si possono realizzare economie di pensiero per le persone che si occupano dei problemi ed economie nella organizzazione dei calcoli concretizzabile nella messa a punto di programmi di elevata adattabilità e di librerie di sottoprogrammi.

Un genere tipico di astrazione riguarda proprietà computazionali che valgono per numeri interi generici: in particolare consideriamo due formule come le seguenti (v. somma di potenze di interi successivi

$\sum_{k=1}^n k = \frac{n(n+1)}{2}$

$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$

In queste formule a sinistra si possono leggere le descrizioni di due procedure che traducono delle esigenze computazionali ben definite (sommare interi progressivi e sommare quadrati di interi progressivi); a destra si possono invece leggere procedimenti di calcolo che ottengono il risultato chiesto con operazioni sensibilmente meno onerose per n elevato. Si tratta quindi di risultati di evidente valore pratico.

Queste formule si dimostrano con considerazioni geometriche che si possono effettuare per numeri interi n grandi quanto si vuole. Esse quindi si possono ottenere senza uscire dall'ambito delle entità effettivamente costribili. Si osserva anche che le espressioni a secondo membro aprono la strada alla individuazione di proprietà generali delle somme di potenze di interi prograssivi.

Si constata tuttavia che cercando di rimanere nell'ambito finito effettivo si è costretti ad usare giri di frase molto elaborati, con evidenti svantaggi in termini di chiarezza dei risultati. Svantaggi anche maggiori si hanno nella chiarezza delle dimostrazioni.

Si trova invece sensibilmente vantaggioso, sia per l'esposizione dei risultati, che per la presentazione delle dimostrazioni, che per la visione di sintesi dei risultati intorno ad un certo argomento, potersi servire di entità non direttamente 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. Infatti risultati come i precedenti si possono dichiarare valere per n arbitrario elemento di un insieme (non finito) e questo comporta già sensibili vantaggi. Altri vantaggi si trovano nelle dimostrazioni di formule come le precedenti, ottenibili con il procedimento di induzione.

D'altra parte coloro che vogliono che i discorsi computazionali riguardino esclusivamente elaborazioni effettivamente realizabili, osservano che sia semplicemente 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.

Occorrre quindi introdurre una nozione di insieme non finito che abbia una giustificazione costruttiva.

[modifica] Procedure illimitate

Le «totalità» sopra accennate possono essere introdotte in modo logicamente rigoroso con la teoria assiomatica degli insiemi. Questa teoria, se si vuole capire a fondo, richiede di affrontare discorsi astratti molto impegnativi. Qu di seguito viene seguita una strada alternativa che presumibilmente può risultare più accettabile a molte persone che vogliono affrontare la matematica solo come giustificazione e inquadramento di procedimenti computazionali nel finito dotati di conseguenze pratiche tangibili.

Per questo scopo occorre introdurre dei meccanismi concretamente realizzabili che chiameremo procedure illimitate. Come tutte le procedure, esse si vogliono in grado di

effettuare operazioni su segni e stringhe che in linea di principio siano

perfettamente riproducibili,

procedere per passi successivi completamente determinati da istruzioni riguardanti operazioni semplici, chiaramente formulate, espresse finitamente e

coinvolgenti dispositivi in grado di memorizzare senza errori le stringhe che vanno elaborando;

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.

Si chiede che sia il complesso delle regole che definiscono una procedura, che ciascuna delle configurazioni che essa può assumere durante le sue evoluzioni si possano 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 per le evoluzioni di una procedura 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 s g m$ ; questo insieme finito di valori corrisponde alla possibilità di realizzare un dispositivo materiale finito capace di distinguere i diversi stati. Quando questa informazione variabile assume il valore $s i$ si dice che la procedura si trova nello stato $s i$ .

Per avere una procedura illimitata si chiede che, qualora si renda necessario nel corso di una evoluzione, essa 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 precisare che si richiedono dispositivi di memoria ampliabili quanto può essere necessario, in modo che la procedura possa prolungare una sua evoluzione quanto serve. Occorre anche 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 a questo proposito si usa anche il termine «infinito», ad es. si parla di «macchine infinite». Per venire incontro alle esigenze di chi si accosta alla matematica con intenti puramente pragmatici (con un atteggiamento antiplatonico) riteniamo opportuno evitare il più possibile il termine «infinito».

Consideriamo per prime (v. [[[tipologia delle elaborazioni e delle procedure]]) le procedure elencative, finalizzate alla emissione di un nastro di risultati, stringa nella quale si individuano successivi identificatori di forma opportuna. Per le procedure elencative illimitate si chiede che il nastro emesso possa fornire un elenco illimitato nel quale si possono individuare quanti si vogliano identificatori.

Per i trasduttori illimitati, procedure trasduttrici in grado di elaborare stringhe immesse in un nastro di ingresso per trasformarle in corrispondenti stringhe presentate su di un nastro di uscita, si chiede che possano elaborare stringhe di ingresso illimitate e possano fornire stringhe di uscita estese quanto si vuole.

Veniamo alle procedure che in seguito alle diverse evoluzioni possono emettere solo due segni, ad es. $t$ e $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 $t$ (o Y, o 1) e le rimanenti che comportano l'emissione del segno $f$ (o N, o 0). Le prime vengono dette stringhe accettate dal meccanismo, le seconde stringhe rifiutate .
Per queste si chiede che possano procedere quanto si vuole nelle loro indagini su stringhe di ingresso estese quanto si vuole.

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. In questo articolo procediamo con minore completezza al fine di giungere più speditamente a giustificare su basi pragmatica l'uso 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 solo un 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 disposizione per risolvere effettivamente problemi di interesse concreto.

Procederemo in modo che ci si possa rendere conto senza gravi difficoltà della possibilità di trovare un buon accordo su cosa sia lecito considerare procedura; inoltre si intendono 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» delle procedure illimitate apre possibilità nelle quali il controllo delle evoluzioni può essere problematico, fino a condurre a situazioni nelle quali si dimostra l'impossibilità di certi controlli.

[modifica] Procedure elencative illimitate

Cerchiamo ora di precisare alcuni tipi di evoluzioni che si possono avere per le procedure elencative illimitate.

Innanzi tutto non si escludono evoluzioni limitate le quali si concludono dopo un numero finito di passi, cioè evoluzioni che subiscono un arresto dopo aver emesso un elenco esplicito. Si possono però avere anche evoluzioni illimitate, evoluzioni che possono compiere tanti passi evolutivi quanti un loro supervisore può volere. In altre parole una evoluzione illimitata, giunta ad un certo passo, non subisce arresto e un suo supervisore può decidere se far proseguire verso nuove configurazioni con un conseguente effettivo allungamento delle stringhe emesse {che possono rivestire interesse), oppure interrompere (al fine di non consumare altre risorse). Sono evoluzioni per le quali si può usare l'espressione abbreviata di «evoluzioni che non si arrestano mai». Inoltre con una sequenza di nuovi passi è assicurata l'emissione di nuovi risultati.

Le evoluzioni elencative illimitate nei casi più favorevoli e proficui procedono nella emissione di elenchi illimitati privi di ripetizioni e costituiti da identificatori che seguono un ordinamento totale chiaramente definibile e verificabile. A questo proposito diciamo evoluzione elencativa illimitata ordinata una evoluzione elencativa illimitata tale che, dati due qualsiasi identificatori diversi che sono stati emessi, si riesce a stabilire quale dei due compare prima dell'altro.

Con altre evoluzioni elencative illimitate si potrebbe avere l'emissione di elenchi illimitati che presentano ripetizioni, oppure per i quali non si possegga un algoritmo che, dati due identificatori emessi qualsiasi, consenta di decidere quale è stato emesso per primo. Queste evoluzioni elencative illimitate non ordinate risultano più problematiche.

Vediamo ora specifiche procedure che consentono di emettere elenchi illimitati ordinati. 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, più particolarmente, le scritture unadiche, le scritture binarie o le scritture decimali dei successivi interi 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 si possono rendere disponibili insiemi dei primi interi naturali estesi quanto si vuole. Per una esigenza si potrebbe generare un nastro con i primi 10 000 interi naturali; per un'altra si potrebbe richiedere l'elenco più esteso dei primi dieci milioni di interi naturali; e così via. Si possono quindi organizzare certe conoscenze su questioni numeriche facendo riferimento ad insiemi finiti ampliabili a richiesta. Ad es. i due elenchi precedenti potrebbero servire per esplicitare rispettivamente i numeri primi inferiori a 10 000 e i numeri primi inferiori a 10 milioni.

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.)

Seguendo questo atteggiamento purista, però, si avrebbero discorsi estremamente pesanti. Risulta molto più conveniente esprimersi facendo riferimento all'esistenza di una entità a sé 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 (qualsiasi).

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 richiesta finitista di trattare solo entità formali effettivamente costruibili, può essere tranquillamente accettata come accorgimento verbale.

Occorre anche giustificare l'utilizzo del termine «insieme» per $\mathbb{N}$ e per altre entità individuabili mediante procedure elencative illimitate ordinate. Una giustificazione consiste nel fatto che, come avremo modo di vedere, per esse si possono considerare gran parte delle nozioni viste per gli insiemi espliciti ed esplicitabili. Perdono senso solo le nozioni legate alla finitezza di questi ultimi.

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

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.