AGGIUNGI PER ORDINARE

C’è un punto filosoficamente significativo della teoria della computazione, che va sottolineato. Così, a buon senso, verrebbe da dire che mettere in ordine qualcosa di più grande è più difficile che mettere in ordine qualcosa di più piccolo. Cioè che la complessità di una situazione cresce con il crescere della sua grandezza. In realtà le cose non stanno così. Basta questo semplice esempio: prendiamo una sedia, 3 tavoli, 8 letti e 4 armadi, se aggiungiamo 3 armadi, 3 tavoli e 4 sedie otteniamo 8 letti, 7 armadi, 6 tavoli e 5 sedie, che è senz’altro più ordinata, benché più grande della situazione precedente.

Una funzione sui numeri naturali è un insieme di coppie ordinate; ad esempio la funzione “fai il quadrato” è l’insieme finito di coppie (1,1), (2,4), (3,9)…I primi elementi sono gli argomenti della funzione e appartengono al suo dominio, i secondi sono i valori e appartengono al suo codominio. Una funzione è calcolabile quando è esprimibile mediante un numero finito di simboli. Ad esempio il quadrato è calcolabile. Ovvero quando una macchina la può calcolare. Un insieme di numeri naturali si dice enumerabile quando esiste una funzione calcolabile che ha come dominio i numeri naturali e come codominio tutti i numeri di quell’insieme. Ad esempio l’insieme dei numeri pari è enumerabile, perché basta moltiplicare per due i numeri naturali per ottenerlo. Attenzione “enumerabile” non significa “numerabile”: è chiaro che tutti gli insiemi enumerabili sono numerabili, ma non è detto che valga il viceversa. Ricordiamo che “numerabile” significa che può essere messo in corrispondenza biunivoca con i numeri naturali. Ora, è evidente che l’unione e l’intersezione di due insiemi enumerabili è enumerabile. Sono teoremi facili da dimostrare. Tuttavia non è detto che un sottoinsieme di un insieme enumerabile sia enumerabile. Anzi gli insiemi infiniti enumerabili possiedono un’infinità di sottoinsiemi propri non enumerabili. Riprendiamo il caso dell’insieme dei numeri pari, che è enumerabile; e consideriamo il suo sottoinsieme infinito 2,6, 12, 56, 78… dove la serie non ha alcuna regola, ad esempio viene prodotta mediante un processo casuale, come il decadimento radioattivo del berillio 11. Tale insieme non è enumerabile, pur essendo un sottoinsieme di un insieme che è, invece, enumerabile. Come nell’esempio precedente dei mobili, il più grande può essere “più ordinato” del più piccolo.

Annunci

Lascia un commento

Archiviato in FILOSOFIA DELLA SCIENZA

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...