definibilita
definibilità termine che designa uno dei principali oggetti di studio della logica matematica, insieme con la dimostrabilità e la calcolabilità; consiste in una riflessione sul concetto [...] di una definizione rigorosa del concetto di → funzione calcolabile; la risposta a questa esigenza è fornita dallʼintroduzione di alcuni modelli di calcolo come la macchina di → Turing, le → funzioniricorsive e il λ-calcolo (→ lambda-calcolo). ...
Leggi Tutto
logica combinatoria
logica combinatoria locuzione utilizzata in due diverse accezioni:
• per indicare un modello di calcolo logico introdotto nel 1920 dal matematico ucraino M.I. Schönfinkel (combinatory [...] la logica combinatoria hanno lo stesso potere espressivo, nel senso che rappresentano la stessa classe di funzioni: le → funzioniricorsive parziali. Il lambda-calcolo ha avuto, nella storia, una diffusione più ampia rispetto alla logica combinatoria ...
Leggi Tutto
fondamenti della matematica
fondamenti della matematica locuzione con la quale si indica, in senso lato, lo studio delle basi epistemologiche della logica e della matematica; in senso stretto, l’espressione [...] a una branca della matematica costituita da uno specifico gruppo di discipline (teoria degli insiemi, teoria delle funzioniricorsive, teoria dei modelli ecc.) ciascuna delle quali, in piena autonomia metodologica, trae la sua origine storica dalle ...
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. [...] calcolabile; allo stesso scopo sono stati introdotti altri modelli di calcolabilità fra i quali le → funzioniricorsive generali e il λ-calcolo (→ lambda-calcolo). Questi modelli di calcolabilità sono equivalenti fra loro in quanto individuano ...
Leggi Tutto
predicato decidibile
predicato decidibile predicato P(x), riferito alla variabile x, per il quale esista una procedura che, data una qualsiasi costante a, permetta di stabilire, in un numero finito di [...] un predicato P è decidibile se e solo se la sua funzione caratteristica è una funzionericorsiva totale, cioè una funzionericorsiva definita per ogni valore della variabile x. La funzione caratteristica di un predicato P si indica con il simbolo ƒP ...
Leggi Tutto
Post, sistema di
Post, sistema di in logica, uno dei modelli sviluppati per proporre una definizione matematica del concetto intuitivo di → funzione calcolabile; altri modelli, tutti tra loro equivalenti, [...] → Turing, le → funzioniricorsive e il → lambda-calcolo. Nel sistema di Post il calcolo di una funzione matematica è simulato dalla un linguaggio formale; da ciò deriva anche la nozione di funzione calcolabile in un sistema di Post. Tale nozione è ...
Leggi Tutto
minimalizzazione, operatore di
minimalizzazione, operatore di o schema della minimalizzazione, una delle regole attraverso le quali si costruiscono le funzioniricorsive. L’operatore di minimalizzazione, [...] delle funzioniricorsive primitive all’insieme delle funzioniricorsive generali. Le più comuni funzioni calcolabili sono infatti primitive ricorsive e per costruirle a partire dalle funzioni base (funzione zero, funzione successore e funzioni di ...
Leggi Tutto
Church, tesi di
Church, tesi di tesi elaborata dal logico statunitense A. Church; afferma che ogni funzione calcolabile è una funzionericorsiva e, viceversa, ogni funzionericorsiva è una funzione calcolabile. [...] con un qualsiasi formalismo l’idea di → calcolabilità, si riesce a dimostrare soltanto l’equivalenza fra le funzioniricorsive e le funzioni calcolabili secondo quel formalismo. La tesi di Church è comunque verificata da tutti i formalismi finora ...
Leggi Tutto
controllo, schema di
controllo, schema di espressione che indica gli schemi costruttivi che sono alla base degli algoritmi. Ogni algoritmo, infatti, può essere costruito utilizzando delle strutture di [...] strutturata. Dato che, secondo la tesi di → Church, ogni procedura algoritmica ha un corrispettivo teorico nell’insieme delle funzioniricorsive, si ha una corrispondenza fra gli schemi di controllo e gli schemi teorici di costruzione delle ...
Leggi Tutto
funzionericorsiva generale
funzionericorsiva generale o funzionericorsiva totale, in logica, → funzionericorsiva definita per ogni numero naturale (o ennupla di numeri naturali nel caso di funzioni [...] ). Se ci sono numeri naturali per i quali la funzione non è definita, essa è detta funzionericorsiva parziale. Funzioniricorsive come l’addizione e la moltiplicazione sono ricorsive totali perché associano a ogni coppia di numeri naturali x ...
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.