La seconda rivoluzione scientifica: matematica e logica. Teoria della ricorsivita
Piergiorgio Odifreddi
Teoria della ricorsività
La teoria della ricorsività affronta lo studio delle funzioni con lo [...] eseguire. Egli si chiese quali operazioni fossero necessarie, e concluse che ci si può restringere a considerare alcune funzioniaritmetiche basilari (somma e prodotto) e alcune operazioni su di esse (ricorsione primitiva e ricerca del minimo, che ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Giorgio Strano
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
Negli anni Trenta del Novecento i logici riescono a dare uno statuto matematico alla [...] è già stata stabilita. Tecnicamente, dunque, le funzioni ricorsive sono gli elementi del più piccolo insieme di funzioniaritmetiche che contiene le funzioni base (funzione zero, funzione successore, funzione proiezione) e che è chiuso rispetto agli ...
Leggi Tutto
funzione calcolabile
funzione calcolabile funzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di [...] l’insieme dei numeri naturali; è, quindi, una funzionearitmetica. L’insieme delle funzioni calcolabili è un sottoinsieme dell’insieme delle funzioniaritmetiche; tuttavia esistono funzioniaritmetiche che non sono calcolabili. Inoltre, mentre le ...
Leggi Tutto
funzionearitmeticafunzionearitmeticafunzione definita sull’insieme N dei numeri naturali. Semplici funzioniaritmetiche sono, per esempio, la funzione successore, definita come s(n) = n + 1 per ogni [...] (ab) = ƒ(a)ƒ(b) per ogni coppia di numeri a e b primi tra loro; è tale per esempio la funzione toziente di → Eulero. Una funzionearitmetica è completamente moltiplicativa se la relazione ƒ(ab) = ƒ(a)ƒ(b) è vera per ogni coppia di numeri naturali non ...
Leggi Tutto
funzione generatrice
funzione generatrice della successione {cn(z)}, è una funzione w(z, t) che ammetta lo sviluppo di → Maclaurin
La funzione generatrice delle partizioni di un insieme di n elementi [...] è data dal prodotto infinito
La funzione ƒ(n) generatrice delle principali funzioniaritmetiche è tuttavia di solito definita diversamente, utilizzando delle serie di → Dirichlet, come la funzione
Per esempio, la funzione toziente di → Eulero è ...
Leggi Tutto
calcolabilita
calcolabilità in logica, termine che indica la possibilità di descrivere in modo sequenziale, deterministico e finito, una procedura di calcolo che consenta di pervenire a un dato risultato. [...] non essere ben definito o non avere termine per gli altri numeri.
L’insieme delle funzioni calcolabili è un insieme numerabile. Tuttavia l’insieme delle funzioniaritmetiche ha una cardinalità maggiore del numerabile: da ciò si deduce che esistono ...
Leggi Tutto
asintotico
asintòtico [agg. (pl.m. -ci) Der. di asintoto] [LSF] (a) Di ciò che tende ad avvicinarsi sempre più a qualche cosa, senza mai raggiungerla o coincidere con essa. (b) Con signif. affine, il [...] a un dato fenomeno (per es., v. oltre: Velocità a.). ◆ [ANM] Aritmetica a.: parte dell'aritmetica che studia le proprietà delle funzioniaritmetiche a., cioè delle funzioni della variabile intera positiva n per le quali si conoscono solo espressioni ...
Leggi Tutto
induzione
Procedimento logico, mediante il quale si passa dalla considerazione di casi particolari a una conclusione generale. In matematica, un insieme A (o una proprietà P) si dice definito per i. [...]
Il principio di i. fornisce la giustificazione per le cosiddette definizioni ricorsive di funzioniaritmetiche. In generale, esse stabiliscono il valore di una funzione per l’argomento zero (e per eventuali parametri); poi verificano il valore della ...
Leggi Tutto
funzione caratteristica
funzione caratteristica per un sottoinsieme S di un insieme X, (S ⊆ X), è la funzione ƒS: X → {0, 1} tale che, per ogni x ∈ X, il suo valore è 1 se x appartiene a S, è 0 altrimenti:
Tale [...] e codominio N ha cardinalità 2N e quindi superiore al numerabile. Ciò implica che non tutte le funzioniaritmetiche sono funzioni calcolabili. Un insieme la cui funzione caratteristica è effettivamente calcolabile è detto insieme ricorsivo. La ...
Leggi Tutto
Kac
Kac Mark propriamente Marek (Kremenec’, oggi Ucraina, 1914 - Los Angeles 1984) matematico statunitense di origine polacca. Ha dato notevoli contributi alla teoria della probabilità, alla meccanica [...] law of errors in the theory of additive number theoretic functions, La legge gaussiana degli errori nella teoria delle funzioniaritmetiche additive) dando così inizio alla teoria probabilistica dei numeri. La sua fama è legata anche al cosiddetto ...
Leggi Tutto
moltiplicazione
moltiplicazióne (ant. multiplicazióne) s. f. [dal lat. multiplicatio -onis]. – 1. L’atto, il fatto di moltiplicare: la m. dei pani e dei pesci, miracolo operato da Gesù, e narrato tre volte nei Vangeli (Matteo 15, 32-38; Marco...
indicatore
indicatóre s. m. (f. -trice) [dal lat. tardo indicator -oris]. – 1. Chi indica; più spesso, dispositivo, apparecchio, scritta o altro elemento che indica o segnala qualche cosa: indicatori di direzione, negli autoveicoli, i lampeggiatori...