funzionecalcolabilefunzionecalcolabilefunzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di [...] a ogni coppia di numeri interi positivi x e y il loro rapporto x : y non è quindi una funzionecalcolabile, bensì semicalcolabile, perché la procedura di calcolo che la definisce è finita in alcuni casi e non lo è in altri. Nel caso della divisione è ...
Leggi Tutto
funzione computabile
funzione computabile altra denominazione di una → funzionecalcolabile, una funzione cioè il cui valore possa essere effettivamente calcolato con un algoritmo. ...
Leggi Tutto
funzione logica
funzione logica detta anche funzione di verità oppure → funzione booleana, associa a uno o più valori di verità in ingresso (vero V e falso F) un solo valore di verità in uscita. Un esempio [...] E.L. Post e va sotto il nome di teorema di completezza funzionale. Da ciò deriva che ogni funzione logica è una funzionecalcolabile perché esiste una procedura algoritmica (rappresentata dalla tavola di verità dell’enunciato a essa associata) che ...
Leggi Tutto
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
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
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] su tali insiemi, è possibile garantire l'applicabilità del teorema del punto fisso di Knaster-Tarski e individuare le funzionicalcolate da programmi ricorsivi come i punti fissi associati a tali programmi.
L'approccio denotazionale ha il pregio di ...
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 [...] che tutti i formalismi erano equivalenti tra di loro nel senso che, per esempio, ogni funzionecalcolabile tramite una macchina di Turing lo era anche mediante le funzioni ricorsive e viceversa. In secondo luogo non si riusciva a trovare nessuna ...
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
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....