Turing, macchina di
Turing, macchina di automa universale, elaborato dal logico inglese A.M. Turing, che fornisce una traduzione formale del concetto intuitivo di → calcolabilità. Sebbene introdotta [...] ck deve essere una configurazione finale.
Una funzione aritmetica ƒ: Nn → N, che a una n-pla di numerinaturali associa un numeronaturale, è calcolabile secondo Turing (o Turing-calcolabile o T-calcolabile) se esiste una macchina di Turing M tale ...
Leggi Tutto
logica intuizionista
logica intuizionista teoria logica nata nel contesto dell’→ intuizionismo, filosofia della matematica elaborata da L.E.J. Brouwer nel 1907. Secondo Brouwer in matematica sono da [...] dalla logica intuizionista in quanto, non avendo un metodo generale per decidere la validità della proposizione G per ogni numeronaturale n, è impossibile affermare che «G è vera oppure ￢G è vera» poiché nessuna delle due è stata dimostrata ...
Leggi Tutto
omotopia
omotopia in topologia algebrica, concetto fondamentale, da cui deriva la relazione di equivalenza sull’insieme degli spazi topologici detta equivalenza omotopica. Dal momento che spazi topologici [...] , il gruppo fondamentale è formato da tutte le potenze intere di c (se n > 0 è un numeronaturale, si può percorrere il ciclo c un numero n di volte ottenendo la potenza n-esima del ciclo, oppure percorrerlo in senso contrario n volte ottenendo la ...
Leggi Tutto
N
N (insieme dei numerinaturali) insieme numerico {0, 1, 2, 3, ...}, indicato con il simbolo N, la cui origine è nell’operazione intuitiva del contare. La nozione di numeronaturale è presente già nelle [...] di «successore di un numeronaturale»:
a) zero è un numeronaturale;
b) se n è un numeronaturale, anche il successore di n è un numeronaturale;
c) se i successori di due numerinaturali sono uguali, allora anche i due numerinaturali sono uguali;
d ...
Leggi Tutto
induzione matematica, principio di
induzione matematica, principio di procedimento che permette di inferire che una certa proprietà P vale per ogni numeronaturale una volta che sia stato dimostrato [...] una volta che sia stato dimostrato che:
• P vale per 0 o per 1 (base dell’induzione);
• per ogni numero n, se P vale per tutti i numerinaturali minori di n, allora P vale anche per n (passo induttivo)».
Il principio di induzione forte deve il suo ...
Leggi Tutto
tipi, teoria dei
tipi, teoria dei in logica, teoria elaborata da B. Russell per superare le antinomie, basate sulla autoreferenzialità, venute alla luce all’epoca della crisi dei → fondamenti della matematica. [...] certa classe di individui (cioè di entità cui non è attribuita nessuna struttura insiemistica) costituisce il tipo 0; inoltre, per ogni numeronaturale n maggiore di 0, la totalità degli insiemi i cui elementi sono di tipo n − 1 costituisce il tipo n ...
Leggi Tutto
Peano, assiomi di
Peano, assiomi di insieme di assiomi che definisce l’insieme N dei numerinaturali e permette di costruire l’aritmetica come sistema ipotetico-deduttivo. La teoria dei numerinaturali, [...] a partire dalle nozioni di «numeronaturale», «zero» e «successore di un numeronaturale», assunti come enti primitivi:
• zero è un numeronaturale;
• se n è un numeronaturale, anche il successore di n è un numeronaturale;
• se i successori di due ...
Leggi Tutto
implicazione
implicazione connettivo logico che corrisponde, nella lingua italiana, all’espressione «se... allora» e si indica con il simbolo ⇒. Dati due enunciati A e B, l’enunciato A ⇒ B (si legge [...] dispari») attraverso i seguenti passaggi:
• se n è dispari, allora può essere scritto nella forma n = 2k + 1, dove k è un numeronaturale;
• allora il quadrato di n è (considerandolo come quadrato di un binomio) n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k ...
Leggi Tutto
predicato
predicato in logica, espressione di una proprietà o di una relazione relativa a una o più costanti o variabili che ne costituiscono gli argomenti. I predicati traducono in espressioni simboliche [...] si legge «per ogni x, x è maggiore o uguale a 0») è vera se x rappresenta un numeronaturale mentre è falsa se x rappresenta un numero negativo; il valore di verità di un predicato dipende dall’insieme in cui sono interpretate le sue variabili, ossia ...
Leggi Tutto
Eulero
Eulèro [STF] Forma italianizz. assai frequente del cognome di L. Euler. ◆ [ALG] [MCC] Angoli di E.: terna di angoli con cui s'individua l'orientamento di un solido intorno a un punto o, che è [...] da E. nel 1758, mentre la prima era già nota a Cartesio (1620). ◆ [ANM] Funzione di E.: per un numeronaturale n, è la funzione φ(n) che dà il numero degli interi positivi non maggiori di n e primi con esso; se la scomposizione di n in fattori dà n ...
Leggi Tutto
numero
nùmero s. m. [dal lat. numĕrus; cfr. novero]. – 1. Ciascuno degli enti astratti che rappresentano insiemi di unità, ordinati in una successione infinita (serie naturale dei n.) nella quale ogni elemento conta un’unità in più rispetto...
naturale
agg. [dal lat. naturalis]. – 1. Della natura, che riguarda la natura o si riferisce alla natura, nel suo sign. più ampio e comprensivo: filosofia n., locuz. con la quale si indicò in passato e si indica tuttora in alcuni paesi l’indagine...