indecidibileindecidìbile [Comp. di in- neg. e decidibile "che non può essere deciso"] [ALG] [FAF] Teoria i.: quella per la quale non esiste nessun algoritmo mediante il quale sia possibile decidere [...] in un numero finito di passi, per ogni proposizione formulabile in essa, se sia vera o falsa; è tale, per es., l'intera aritmetica (v. Gödel, teorema di: III 53 c) ...
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 [...] teoria oppure no, 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 ...
Leggi Tutto
problema dell’arresto
Fabrizio Luccio
Primo esempio di problema indecidibile, cioè che non ammette alcun algoritmo di risoluzione. Il problema dell’arresto nacque nel 1936, sulla base di studi sugli [...] insiemi infiniti della fine del XIX sec. La sua enunciazione è dovuta ad Alan Turing ed è basata sulla formalizzazione dei modelli primitivi di calcolo sviluppati all’inizio di quel secolo, tra cui la ...
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 [...] oppure no, 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 ...
Leggi Tutto
Arti e tecnica: scenari futuri
Massimo Carboni
Quale sarà il ruolo delle arti nella semiosfera telematica e digitale? Quanto della loro costitutiva e preziosa ambiguità semantica, del senso indecidibile [...] di cui ci consegnano la fruttuosa esperienza, abdicherà alla logica binaria del computer? Nell’ambito della riflessione storico-critica attuale, il rapporto tra le neotecnologie e le arti contemporanee ...
Leggi Tutto
trivalente
trivalènte [agg. Comp. di tri- e valente] [CHF] Di elemento chimico che ha valenza tre, cioè che presenta trivalenza. ◆ [ALG] [FAF] Logica t.: quella nella quale si ammette che una proposizione [...] possa essere o vera o falsa o indecidibile. ...
Leggi Tutto
Matijasevic
Matijasevič Jurij Vladimirovič (Leningrado, oggi San Pietroburgo, 1947) matematico russo. Il suo nome è legato alla soluzione (in negativo) del decimo problema di Hilbert sulla risolubilità [...] di una equazione diofantea. Dimostrò nel 1970 che il problema è indecidibile nella sua tesi di dottorato al lomi (Dipartimento di Leningrado dell’Istituto Steklov di Matematica dell’Accademia russa delle scienze). Nell’ambito di questo dipartimento è ...
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
indecidibile
indecidìbile agg. [der. di decidere, col pref. in-2]. – Propr., che non può essere deciso. In logica, è detto di ogni asserzione, proposizione, formula per la quale si dimostra che, in un dato sistema formalizzato, né essa né...
indecidibilita
indecidibilità s. f. [der. di indecidibile]. – L’essere indecidibile. In logica, condizione nella quale è impossibile decidere se una proposizione è vera o falsa.