decidibilitadecidibilità 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 [...] p(x) è decidibile, allora la funzione ƒ deve essere una funzione calcolabile; per questo motivo il problema della decidibilità è strettamente collegato al tema della calcolabilità di una funzione.
Un calcolo logico è detto decidibile qualora si ...
Leggi Tutto
indecidibilita
indecidibilità in logica, termine utilizzato per indicare la non → decidibilità di una data proprietà. In particolare, un insieme è indecidibile se non esiste un algoritmo in grado di [...] di → Zermelo-Fraenkel. È importante distinguere il concetto di teoria indecidibile dalla nozione di formula indecidibile (→ decidibilità). Un esempio di enunciato indecidibile è quello espresso nel decimo problema di Hilbert, relativo alle equazioni ...
Leggi Tutto
Matematica e logica matematica (Saint Louis 1919 - ivi 1985), dal 1976 prof. di matematica all'univ. della California a Berkeley. Si è interessata di logica matematica (funzioni ricorsive e problemi di [...] decidibilità) e di teoria dei numeri. Di particolare importanza la scoperta (completata da J. V. Matijasević nel 1970) dell'indecidibilità del 10º problema di D. Hilbert: non esiste un metodo generale effettivo per decidere se una equazione diofantea ...
Leggi Tutto
Matematico russo (Mosca 1901 - ivi 1975). Il suo nome è legato a ricerche di algebra, di teoria della misura, di teoria degli insiemi, di logica matematica, di teoria degli algoritmi, di matematica intuizionista [...] e di questioni di decidibilità. Ha insegnato nell'univ. di Mosca e ha tenuto per molti anni la cattedra di analisi matematica all'Istituto di pedagogia V. I. Lenin di Mosca. Uno dei suoi più celebri risultati è la dimostrazione che non sempre esiste ...
Leggi Tutto
INFORMATICA
Paolo Ercoli
Alberto Marini
Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni [...] , New York 1974; W.S. Brainerd, L. H. Landweber, Theory of computation, ivi 1974; Hermes, Enumerabilità decidibilità computabilità, Torino 1975; V. P. Preparata, R. T. Yeh, Introduzione alle strutture discrete, ivi 1976.
Informatica matematica ...
Leggi Tutto
Un insieme I si dice e. quando esiste un procedimento effettivo (➔ decisione) per stabilire una corrispondenza biunivoca tra I e l’insieme dei numeri naturali (nell’insieme numerabile invece non viene [...] posta una condizione di effettiva costruibilità della corrispondenza).
Valgono tra i concetti di decidibilità, computabilità ed enumerabilità le relazioni: a) un insieme I è decidibile se e solo se sia I che il suo complemento sono e.; b) un insieme ...
Leggi Tutto
refutazione
refutazione di una formula in un sistema formale, è la dimostrazione della sua negazione. In un sistema formale, se una formula A non è deducibile e non è refutabile (cioè anche non A non [...] è deducibile) allora la formula è indecidibile (→ decidibilità). Più in generale, il termine può riferirsi alla non accettazione di una congettura, che può essere refutata esibendone un controesempio. Un metodo per determinare se una proposizione va ...
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 [...] P(a), ottenuto dalla sostituzione della costante a alla variabile x, è vero o falso (→ algoritmo). La decidibilità di un predicato, basandosi sull’esistenza di un procedimento algoritmico, è strettamente legata al tema della → calcolabilità. Per ...
Leggi Tutto
teoria indecidibile
teoria indecidibile in logica, teoria formalizzata in un sistema formale S per la quale non per ogni formula ben formata a di S esiste un algoritmo di calcolo che riesce a stabilire [...] vale a dire se a è o non è dimostrabile nel sistema formale dato. Esempi di teorie indecidibili sono l’aritmetica formalizzata dagli assiomi di → Peano e la teoria degli insiemi formalizzata secondo gli assiomi di → Zermelo-Fraenkel (→ decidibilità). ...
Leggi Tutto
decidibilita
decidibilità s. f. [der. di decidibile]. – La qualità o la condizione di essere decidibile, sia in senso generico, sia nel sign. specifico della logica matematica.