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 [...] le mosse dalle antinomie riportate e viene estesa ad aree di ricerca contigue, quali per esempio la teoriadellacalcolabilità, la teoria degli insiemi e lʼinformatica teorica. Per quanto riguarda lʼinformatica teorica, il concetto di definibilità è ...
Leggi Tutto
quadratura
quadratura in geometria, procedura consistente nel costruire un quadrato equivalente a una figura piana assegnata. Il problema della quadratura ha particolare interesse, sia storico sia matematico, [...] matematica greca di risolvere tale problema mediante riga e compasso è un primo modello di teoriadellacalcolabilità, essendo riga e compasso strumenti perfettamente formalizzabili. Per eseguire tale costruzione i greci stessi conoscevano metodi ...
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 [...] elemento appartiene o meno a esso. In questo senso il concetto di insieme indecidibile è strettamente collegato alla teoriadella → calcolabilità. Una teoria formalizzata in un sistema formale S è indecidibile se lo è l’insieme dei suoi teoremi, se ...
Leggi Tutto
matematica discreta
matematica discreta settore di studi della matematica che tratta oggetti che possono assumere solo valori discreti (in pratica numeri interi). La maggior parte di questi oggetti, [...] calcolo combinatorio, la → logica, la teoria degli → insiemi, la → crittografia, la teoria dei → numeri, la teoria dei → grafi, l’→ informatica, lo studio degli → algoritmi, la teoriadella → calcolabilità, lo studio delle catene di → Markov e quello ...
Leggi Tutto
automa universale
automa universale espressione utilizzata per indicare un automa in grado di calcolare i valori di una qualsiasi funzione calcolabile. In teoriadellacalcolabilità è sinonimo di → algoritmo. [...] L’esempio fondamentale di automa universale è quello introdotto da A.M. Turing (→ Turing, macchina di) ...
Leggi Tutto
Costa
Costa Newton Carneiro Affonso da (Curitiba 1929) matematico e logico brasiliano. È noto soprattutto per i suoi lavori di → logica paraconsistente e le relative applicazioni in teoriadellacalcolabilità, [...] e in intelligenza artificiale ...
Leggi Tutto
Insieme delle scienze che studiano in modo ipotetico-deduttivo entità astratte come i numeri e le misure: la m. pura studia i problemi matematici indipendentemente dalla loro utilizzazione pratica; alla [...] la prima volta superati i limiti delle conoscenze matematiche dei Greci, con la risoluzione e la teoriadelle equazioni di 3° e 4° algoritmo, di programma, di calcolabilità, e con le ricerche nel campo dell’intelligenza artificiale. Il programma ...
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, [...] Subject Classification. Essa mostra rinvii dalla combinatoria alla logica matematica e ai fondamenti (calcolabilità e teoriadella ricorsività), a ordini, reticoli, strutture algebriche ordinate (aspetti algebrici degli insiemi parzialmente ordinati ...
Leggi Tutto
(o computer, o elaboratore elettronico) Apparecchio o dispositivo utilizzato per l’elaborazione di dati e segnali.
Cenni storici
Le origini
Il desiderio di realizzare uno strumento in grado di compiere [...] nella definizione dellateoria dei servomeccanismi (H.L. Hazen, 1934) e con la presentazione di una metodologia per il progetto logico dei circuiti digitali (C. Shannon, 1937). Di fondamentale importanza nel campo dellacalcolabilità furono gli ...
Leggi Tutto
(II, p. 421; App. II, I, p. 125; III, I, p. 61; IV, I, p. 83)
Negli ultimi dieci anni lo sviluppo dell'a. è stato molto vivace. Ai temi di ricerca già consolidati se ne sono aggiunti nuovi e ne sono stati [...] critica sui concetti stessi di effettività e calcolabilità. Di fatto gli algoritmi tipici del calcolo 1970 dal fisico M. Virasoro. La costruzione con cui tale a. appare nella teoriadelle a. di Kac-Moody è di nuovo suggerita dalla fisica ed è detta '' ...
Leggi Tutto