La grande scienza. Combinatoria
Peter J. Cameron
Combinatoria
Secondo alcuni la combinatoria costituisce soltanto una parte della matematica, secondo altri essa non rappresenta una branca separata, [...] piccolo). Tale enunciato non è dimostrabile dagli assiomi in quanto la corrispondente 'funzione di Paris-Harrington' cresce più rapidamente di ogni funzionecalcolabile. Sono stati scoperti numerosi altri esempi di questo fenomeno, la maggior parte ...
Leggi Tutto
La grande scienza. Intelligenza artificiale
Marco Somalvico
Francesco Amigoni
Viola Schiaffonati
Intelligenza artificiale
In questa trattazione viene presentata l'intelligenza artificiale (nel seguito [...] adattativo alle sollecitazioni dell'ambiente modificando il proprio comportamento. Uno dei risultati è quello di mostrare come ogni funzionecalcolabile possa essere elaborata da una qualche rete di neuroni connessi. A partire da ciò nel 1949 Donald ...
Leggi Tutto
Intelligenza artificiale
Francesco Amigoni
Viola Schiaffonati
Marco Somalvico
L’intelligenza artificiale è una disciplina recente che negli anni ha fornito un importante contributo al progresso dell’intera [...] sollecitazioni dell’ambiente modificando il proprio comportamento. Uno dei risultati più significativi consentì di mostrare come ogni funzionecalcolabile potesse essere elaborata da una qualche rete di neuroni connessi. A partire da ciò, nel 1949 ...
Leggi Tutto
Matematica: problemi aperti
Claudio Procesi
Prima di parlare dei problemi aperti nella matematica è bene riflettere su quelli che ne hanno segnato la storia passata. Sono infatti proprio questi che [...] un analogo in termini di linguaggi. Si introduce quindi un preordine in cui L≤pL′, con L⊂∑ e L′⊂∑′, se esiste una funzionecalcolabile in tempo polinomiale f:∑→∑′ con la proprietà
[8] w∈L f(w)∈L′.
Con questa definizione, un linguaggio L si dice NP ...
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 [...] Cantor (1845-1918).
Nei primi anni Trenta ci si cominciò a chiedere quale fosse allora la classe delle funzionicalcolabili. Alonzo Church, Kurt Gödel, Emil L. Post, Alfred Tarski e Alan M. Turing proposero diverse possibili definizioni. Ciascuna ...
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 [...] e originale lascito intellettuale della logica novecentesca. Gli anni Trenta sono cruciali per chiarire la nozione di funzionecalcolabile e di procedura finita, e, in generale, per gettare le basi della teoria matematica della calcolabilità, molto ...
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 [...] parziali. Ciò implica che il lambda-calcolo può essere considerato, al pari delle funzioni ricorsive o della macchina universale di Turing, un modello di calcolo in grado di tradurre in termini rigorosi il concetto intuitivo di funzionecalcolabile. ...
Leggi Tutto
ricorsivita
ricorsività in logica, caratteristica di un procedimento che riduce la complessità di un problema riportandolo a problemi via via più semplici cui il procedimento stesso viene applicato. [...] senso matematicamente rigoroso, il concetto intuitivo di → funzionecalcolabile, per la quale cioè esista un procedimento (→ algoritmo) che calcoli, in un numero finito di passi, il valore della funzione in uscita in corrispondenza di ogni valore in ...
Leggi Tutto
formula decidibile
formula decidibile in un calcolo logico, formula ben formata a tale che o essa stessa o la sua negazione ￢a (si legge «non a») siano dimostrabili formalmente in tale calcolo. Ciò equivale [...] ￢a siano dimostrabili all’interno dell’aritmetica stessa. La decidibilità di una formula comporta la possibilità di definire una funzionecalcolabile ƒ che assume un certo valore, per esempio 1, se l’espressione rappresentata dalla formula è vera, e ...
Leggi Tutto
regola ricorsiva
regola ricorsiva regola che, nella propria formulazione, “richiama sé stessa”. Tale richiamo non è tuttavia una sorta di circolo vizioso perché una regola ricorsiva definisce un oggetto [...] . Il principio alla base delle regole ricorsive è applicato anche nella definizione di una importante classe di funzioni, le → funzioni ricorsive, le quali hanno il ruolo di tradurre in termini formali il concetto intuitivo di funzionecalcolabile. ...
Leggi Tutto
calcolabile
calcolàbile agg. [der. di calcolare]. – Che può essere calcolato. In matematica, funzione c., funzione che può essere calcolata, per la quale esiste cioè un procedimento effettivo per calcolare il suo valore per dati valori dei...
funzione
funzióne s. f. [dal lat. functio -onis, der. di fungi «adempiere»]. – 1. Attività svolta abitualmente o temporaneamente in vista di un determinato fine, per lo più considerata nel complesso di un sistema sociale, burocratico, ecc....