INFORMATICA
Paolo Ercoli
Alberto Marini
Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni [...] T-computabili coincidono con altre due classi di funzioni proposte come totalità delle funzioni calcolabili, cioè con le funzioni definibili con il cosiddetto "λ-calcolo" di A. Church e con le funzioni generali ricorsive di K. Gödel. In ogni caso le ...
Leggi Tutto
lambda-calcolo
lambda-calcolo o λ-calcolo o L-calcolo, modello di calcolo introdotto negli anni Trenta del secolo scorso da A. Church allo scopo di rappresentare formalmente il procedimento di computazione [...] nell’ambito del λ-calcolo il calcolo di una classe di funzioni. È possibile dimostrare che le funzioni rappresentabili nel λ-calcolo sono tutte e sole le → funzioniricorsive, le quali sono calcolabili anche con il modello della macchina universale ...
Leggi Tutto
STORIA DELLA MATEMATICA
Luigi Borzacchini
STORIA DELLA MATEMATICA
Il tempo della scienza senza tempo
La matematica è la più antica e la più immutabile delle discipline. Si può dire che la matematica [...] di tale concetto portò negli anni Trenta e Quaranta a innumerevoli soluzioni, tra cui le macchine di Turing, le funzioniricorsive, il λ-calcolo.
Anche negli algoritmi la semantica aveva un doppio regime: il significato di una primitiva del ...
Leggi Tutto
Cibernetica
Ernest H. Hutten
di Ernest H. Hutten
Cibernetica
sommario: 1. Introduzione storica. 2. L'epistemologia delle macchine. 3. La struttura informativa delle macchine. 4. Sistema, processo, informazione [...] e generali, di ricorsività o di procedimenti iterativi; alla fine, si è arrivati al concetto molto ampio di funzionericorsiva generale, in cui non appare più l'elemento iterativo (Herbrand-Gödel-Kleene). Il concetto di ricorsività generale precisa ...
Leggi Tutto
Intuizionismo
AArend Heyting
di Arend Heyting
Intuizionismo
sommario: 1. Concetti fondamentali. 2. Aritmetica elementare. 3. Il principio del terzo escluso. 4. I numeri reali. 5. Ineguaglianza e separazione [...] al metodo di costruzione di un numero naturale.
Una soluzione fu resa possibile dalla teoria delle funzioniricorsive. L'analisi ricorsiva è diventata un importante campo di ricerca, in cui sono stati ottenuti risultati molto fecondi dai matematici ...
Leggi Tutto
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] f tale che f(x) è il minimo intero m per il quale g(x,m)=0.
È un risultato classico che le funzioniricorsive e le macchine di Turing, come pure molti altri formalismi, definiscono le stesse classi di oggetti computabili. Che esse corrispondano a ciò ...
Leggi Tutto
Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] tale che f(x) è il minimo intero m per il quale g(x,m)=0. È un risultato classico che le funzioniricorsive e le macchine di Turing, come pure molti altri formalismi, definiscano le stesse classi di oggetti computabili. Secondo la cosiddetta tesi di ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. I teoremi di incompletezza di Godel
Carlo Cellucci
I teoremi di incompletezza di Gödel
Nei giorni 5-7 settembre 1930 ebbe luogo a Königsberg [...] con quella più debole della coerenza (Rosser 1936) e da Stephen C. Kleene in termini della teoria delle funzioniricorsive (Kleene 1936). Nel 1939 apparve il secondo volume dell'opera di David Hilbert e Paul Bernays, Grundlagen der Mathematik ...
Leggi Tutto
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 [...] su di esse (ricorsione primitiva e ricerca del minimo, che definiremo più avanti). Egli aveva dunque concepito la nozione di funzionericorsiva nel senso moderno, e un analogo di quella che si chiama tesi di Church, cioè l'asserzione che la nozione ...
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 [...] un suggerimento di Jacques Herbrand, Kurt Gödel arriva a definire la nozione generale di funzionericorsiva. Del resto risultati sulle funzioniricorsive erano stati già sviluppati da Gödel nella sua fondamentale memoria del 1931.
Informalmente, l ...
Leggi Tutto
ricorsivo
agg. [der. di ricorrere]. – In matematica e in logica matematica, sinon. di ricorrente (nel sign. 3 c); in partic., nella teoria della ricorsività, funzioni r. primitive, quelle che si possono ottenere dalle funzioni iniziali mediante...
definibilita
definibilità s. f. [der. di definibile]. – Possibilità di essere definito. In matematica e in logica matematica, la proprietà che ha un ente di essere calcolabile, per es. mediante funzioni ricorsive.