Termine con cui è anche chiamata l'algebra combinatoria, disciplina che studia, piuttosto che le strutture algebriche classiche (gruppo, anello, corpo, ecc.), le strutture algebriche di tipo più semplice, [...] Tale enunciato non è dimostrabile a partire 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 di ...
Leggi Tutto
LOGICA MATEMATICA
Aldo Marruccelli
Alberto Pasquinelli
(XXI, p. 398; App. II, 11, p. 226; III, 1, p. 999).
Princìpi di logica matematica.
È opportuno premettere all'articolo che dà notizia dei progressi [...] di deduzione o di dimostrazione. L'insieme delle regole d'inferenza è sempre finito. Ogni regola d'inferenza è una funzionecalcolabile che consente di dedurre una fbf a partire da una o più fbf (sempre in numero finito). Una "dimostrazione" nella ...
Leggi Tutto
Undicesima lettera dell’alfabeto greco (maiuscolo Λ, minuscolo λ), corrispondente alla consonante latina l.
biologia Fago l. Batteriofago che ha come ospite il batterio Escherichia coli. Su di esso sono [...] in modo tale che a ogni espressione corrisponda un procedimento di calcolo ben definito; viceversa a ogni funzionecalcolabile corrisponde un’espressione nel l. calcolo. Quest’ultimo può quindi essere considerato un linguaggio di programmazione ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1961-1970
1961-1970
1961
Famiglia universale. Il giapponese Masatake Kuranishi mostra che esiste sempre un certo tipo di famiglia olomorfa di strutture complesse [...] da Church negli anni Trenta, è una formalizzazione del concetto di funzionecalcolabile. Ogni termine del λ-calcolo rappresenta sia una funzione sia un argomento di funzione; il termine MN rappresenta l'applicazione del termine M (visto come ...
Leggi Tutto
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
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
La seconda rivoluzione scientifica: matematica e logica. L'intuizionismo di Brouwer
Anne L. Troelstra
L'intuizionismo di Brouwer
Nella dissertazione Over de Grondslagen der Wiskunde (I fondamenti della [...] inizi degli anni Quaranta Kleene concepì un'interpretazione che stabiliva una connessione fra la nozione di funzionecalcolabile (ricorsiva) e logica intuizionista, l'interpretazione di realizzabilità (Kleene 1945). L'idea dell'interpretazione è di ...
Leggi Tutto
calcolabilecalcolàbile [agg. Der. di calcolo] [ALG] Funzione c.: funzione che può essere calcolata, per la quale pertanto esiste un procedimento effettivo (cioè un algoritmo) per determinare il suo [...] valore quando sia assegnato il suo argomento (o i suoi argomenti) ...
Leggi Tutto
Matematico e logico-matematico statunitense (Washington 1903 - Hudson, Ohio, 1995), prof. di matematica (1947-61), poi di matematica e filosofia (1961-67) a Princeton, dal 1967 di matematica e filosofia [...] di Post. La tesi di Ch. e l'affermazione inversa (cioè ogni funzione ricorsiva è effettivamente calcolabile) precisano la nozione di procedimento effettivo di calcolo nel caso di funzioni di numeri naturali. La tesi di Ch. non si può né dimostrare ...
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....