ordine
órdine [Der. del lat. ordo -inis] [LSF] (a) Disposizione regolare di più cose secondo una regola prefissata; (b) il grado più o meno grande di organizzazione interna di un sistema complesso, relativ. [...] fase, transizioni di: II 538 f. ◆ [ALG] O. di un corpo algebrico finito: → corpo. ◆ [ANM] O. di un'equazione differenziale: l'o. maggiore tra 'o. di un insieme: il criterio in base al quale si effettua l'ordinamento (←) di un insieme. ◆ [MCS] ...
Leggi Tutto
euclideo
euclidèo [agg. Der. di Euclide] [ALG] [FAF] Qualifica di ente matematico o di sistema ipotetico-deduttivo che soddisfi i postulati di Euclide. ◆ [ALG] Algoritmo e. delle divisioni successive: [...] numeri, e anche di due polinomi, attraverso un numero finito di operazioni di divisione: → algoritmo. ◆ [ALG] chiamato il gruppo delle traslazioni nello spazio. ◆ [ALG] Intorno e.: insieme dei punti aventi da un punto dato P distanza minore di un ...
Leggi Tutto
aritmetica di Presburger
Luca Tomassini
Versione semplificata dell’aritmetica di Peano, ottenuta da quest’ultima eliminando l’operazione di moltiplicazione. Più precisamente, l’aritmetica di Presburger [...] si paga un prezzo molto alto: esso è sostituito da un insieme infinito di assiomi, uno per ciascuna proprietà P. La caratteristica ‘assiomi di induzione’ di cui sopra con un numero finito di altri assiomi ottenendo una teoria con gli stessi identici ...
Leggi Tutto
teorema di compattezza
Silvio Bozzi
Nella logica matematica, è tale un qualsiasi teorema che stabilisce che – fissato un linguaggio formale L – una teoria T ha come conseguenza logica la formula A, [...] teoria T ha un modello se ne ha uno ogni sua parte finita. Il teorema vale per i linguaggi elementari di qualunque cardinalità dei linguaggi si generalizzi il concetto di finito a quello di elemento di un insieme ammissibile. Come provato da Jerome ...
Leggi Tutto
calcolabilità
Fabrizio Luccio
La teoria che studia la possibilità di calcolare una funzione dagli interi sugli interi mediante un modello astratto di computazione come per es. la macchina di Turing. [...] interi) mentre le funzioni appartengono a un insieme non numerabile: questo implica che devono esistere funzioni ingresso un altro algoritmo A arbitrario e dati arbitrari D per esso, stabilisca in tempo finito se il calcolo di A su D termina in tempo ...
Leggi Tutto
computabile
computàbile [agg. Der. dell'ingl. computable, che è dal lat. computabilis "che si può calcolare", "di cui si può o si deve tenere conto", già reso con l'it. calcolabile] [ALG] [FAF] [INF] [...] Di una variabile (per es., l'insieme dei numeri naturali) che si può calcolare effettivamente, cioè per la la quale è possibile trovare un procedimento per calcolarne, con un numero finito di passi, il valore per ogni n-upla di valori delle variabili ...
Leggi Tutto
proprio
pròprio [Der. del lat. proprius, probab. dalla locuz. pro privo "a titolo privato"] [LSF] Conserva il signif. di proprietà e quindi con signif. affine a quello di peculiare, specifico e simili. [...] a improprio (per es., punto p. cioè non improprio e quindi punto al finito; analogamente per retta p., piano p., ecc.) o a generico, in senso Classe p.: ogni insieme che non possa essere considerato come facente parte di un altro insieme. ◆ [ALG] ...
Leggi Tutto
compattezza
compattézza [Der. di compatto "l'essere compatto" nei vari signif. del termine (→ compatto)] [FAF] Teorema di c.: uno dei più importanti risultati della teoria dei modelli: un insieme di [...] formule non contraddittorio ha un modello se, e solo se, ogni suo sottoinsieme finito ha un modello: v. logica: III 485 d. ...
Leggi Tutto
insieme
insième (ant. insème) avv. e s. m. [lat. ĭnsĕmul, rifatto nel lat. volg. in *insĕmel per sostituzione di semel «una volta» a simul «insieme»]. – 1. avv. Esprime in genere i seguenti rapporti: a. Compagnia, unione: siamo usciti i. io...
finito
agg. [part. pass. di finire]. – 1. a. Giunto o condotto a termine, compiuto: arrivare a spettacolo f.; sono ormai due anni f. che ha lasciato il paese. Frequente nell’uso fam. la locuz. farla finita (con la indeterminato), smettere...