Ackermann, funzione di
Ackermann, funzione di esempio di → funzione ricorsiva che non è ricorsiva primitiva (→ funzione ricorsiva primitiva). Hilbert formulò l’ipotesi che ogni funzionecalcolabile fosse [...] di composizione e ricorsione. Tale affermazione si rivelò infondata quando nel 1928 Ackermann definì una nuova funzionecalcolabile, ma non ricorsiva primitiva, poiché per ottenerla è necessario un ulteriore procedimento, detto di minimalizzazione ...
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
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 [...] W.V. Quine.
Vicina al tema della definibilità è anche la riflessione sulla calcolabilità e la ricerca di una definizione rigorosa del concetto di → funzionecalcolabile; la risposta a questa esigenza è fornita dallʼintroduzione di alcuni modelli di ...
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. [...] ƒ: N → N), per la quale sia definito un algoritmo che calcoli i valori della funzione stessa. Si distinguono funzionicalcolabili totali e funzionicalcolabili parziali:
• una funzionecalcolabile si dice totale se è definita per ogni numero naturale ...
Leggi Tutto
algebra combinatoria
algebra combinatoria o combinatoria algebrica, settore di studi che utilizza metodi combinatori, cioè di ordinamento e conteggio, per lo studio di problemi algebrici o, viceversa, [...] tale enunciato non è dimostrabile a partire dagli assiomi in quanto la corrispondente funzione che ne realizzerebbe la dimostrazione cresce più rapidamente di ogni funzionecalcolabile. È un risultato non dissimile da quello a cui era giunto K. Gödel ...
Leggi Tutto
decidibilita
decidibilità termine utilizzato nella teoria della calcolabilità per indicare l’esistenza di una procedura algoritmica che permetta di stabilire, in un numero finito di passi, se una data [...] (3) = 0, ƒ(14) = 1, …). Occorre sottolineare che, se la formula p(x) è decidibile, allora la funzione ƒ deve essere una funzionecalcolabile; per questo motivo il problema della decidibilità è strettamente collegato al tema della calcolabilità di una ...
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 [...] il concetto di procedura algoritmica e di funzionecalcolabile. Si dice pertanto che un predicato P è decidibile se e solo se la sua funzione caratteristica è una funzione ricorsiva totale, cioè una funzione ricorsiva definita per ogni valore della ...
Leggi Tutto
Post, sistema di
Post, sistema di in logica, uno dei modelli sviluppati per proporre una definizione matematica del concetto intuitivo di → funzionecalcolabile; altri modelli, tutti tra loro equivalenti, [...] può essere considerato come una grammatica generatrice di un linguaggio formale; da ciò deriva anche la nozione di funzionecalcolabile in un sistema di Post. Tale nozione è equivalente alla calcolabilità secondo il modello della macchina di Turing ...
Leggi Tutto
Church, tesi di
Church, tesi di tesi elaborata dal logico statunitense A. Church; afferma che ogni funzionecalcolabile è una funzione ricorsiva e, viceversa, ogni funzione ricorsiva è una funzionecalcolabile. [...] qualsiasi formalismo l’idea di → calcolabilità, si riesce a dimostrare soltanto l’equivalenza fra le funzioni ricorsive e le funzionicalcolabili secondo quel formalismo. La tesi di Church è comunque verificata da tutti i formalismi finora conosciuti ...
Leggi Tutto
enumerabile
enumerabile termine che si riferisce a un insieme di cui sia possibile elencare tutti gli elementi in un dato ordine. Tale insieme deve quindi essere finito o numerabile, ma ciò non è sufficiente. [...] infiniti successivi. In termini più formali, un insieme è enumerabile se risulta essere l’immagine di una funzionecalcolabile. L’aggettivo è utilizzato anche nel contesto della decidibilità dell’appartenenza di un elemento a un insieme infinito ...
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....