Informazione e computazione quantistica: teoria
Mario Rasetti
Al crocevia tra scienza e tecnologia
La nuova disciplina che va sotto il nome di informazione e computazione quantistica si sviluppa al [...] spazio completo degli stati) che è la sovrapposizione uniforme di stati della forma ∣x⟩∣f(x)⟩. Il calcolo di una qualsiasi funzionericorsiva booleana che, come f(x), si possa ricondurre a una permutazione, è sempre equivalente a una sequenza (la cui ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. L'intuizionismo di Brouwer
Anne L. Troelstra
L'intuizionismo di Brouwer
Nella dissertazione Over de Grondslagen der Wiskunde (I fondamenti della [...] (m,k) e k realizza B(m).
Qui ∙ è l'operazione di applicazione tra un numero e il codice di una funzionericorsiva parziale. Kleene stabilì la correttezza di questa interpretazione: se HA ⊦A, allora esiste un numero n che realizza A. In particolare ...
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 [...] un predicato P è decidibile se e solo se la sua funzione caratteristica è una funzionericorsiva totale, cioè una funzionericorsiva definita per ogni valore della variabile x. La funzione caratteristica di un predicato P si indica con il simbolo ƒP ...
Leggi Tutto
minimalizzazione, operatore di
minimalizzazione, operatore di o schema della minimalizzazione, una delle regole attraverso le quali si costruiscono le funzioniricorsive. L’operatore di minimalizzazione, [...] delle funzioniricorsive primitive all’insieme delle funzioniricorsive generali. Le più comuni funzioni calcolabili sono infatti primitive ricorsive e per costruirle a partire dalle funzioni base (funzione zero, funzione successore e funzioni di ...
Leggi Tutto
predecessore
predecessore o precedente, di un numero naturale n non nullo indica il numero che viene immediatamente prima di n nell’usuale ordinamento di N: 0, 1, 2, 3… Per esempio il predecessore di [...] , per convenzione, che il predecessore di 0 sia 0 stesso (p(0) = 0). La funzione p(n) è una → funzionericorsiva primitiva. Essa può essere definita usando le funzioni di base proiezione (indicata con il simbolo P12(m, n)), che associa a ogni coppia ...
Leggi Tutto
proiettore
proiettore termine utilizzato sia in analisi sia in logica.
☐ In analisi, si dice proiettore in uno spazio vettoriale X un operatore lineare P tale che P 2 = P. Questa nozione generalizza [...] variare di w in V.
☐ In logica, è così detta una delle funzioni di base che si utilizzano per la costruzione di una → funzionericorsiva. Le funzioni di proiezione o funzioni proiettore associano a ogni n-upla ordinata di numeri naturali (x1, …, xn ...
Leggi Tutto
Church, tesi di
Church, tesi di tesi elaborata dal logico statunitense A. Church; afferma che ogni funzione calcolabile è una funzionericorsiva e, viceversa, ogni funzionericorsiva è una funzione calcolabile. [...] con un qualsiasi formalismo l’idea di → calcolabilità, si riesce a dimostrare soltanto l’equivalenza fra le funzioniricorsive e le funzioni calcolabili secondo quel formalismo. La tesi di Church è comunque verificata da tutti i formalismi finora ...
Leggi Tutto
insieme ricorsivamente enumerabile
insieme ricorsivamente enumerabile insieme tale che, dato un elemento a, è possibile stabilire, in un numero finito di passi, se esso gli appartenga. Se tuttavia l’elemento [...] alla semidecidibilità (→ insieme decidibile). In termini più rigorosi, un insieme è ricorsivamente enumerabile se e solo se è vuoto oppure è il codominio di una funzionericorsiva totale; ciò equivale a dire, se si accetta la tesi di → Church ...
Leggi Tutto
insieme decidibile
insieme decidibile in logica, insieme per cui esiste un algoritmo di calcolo che permette di stabilire in un tempo finito se, dato un elemento a, l’elemento appartiene o non appartiene [...] si può affermare che un insieme S è decidibile o ricorsivo se la sua funzione caratteristica ƒ(x) è una funzionericorsiva, dove per funzione caratteristica si intende la funzione definita come segue:
Dato un predicato decidibile P, l’insieme ...
Leggi Tutto
predicato semidecidibile
predicato semidecidibile in logica, predicato P(x) per il quale si riesce a stabilire, con un numero finito di operazioni, se esso è vero, mentre non esiste una procedura finita [...] per stabilire se esso è falso. La funzione caratteristica di un predicato semidecidibile è, quindi, definita solo per alcuni valori della variabile x ed è pertanto una funzionericorsiva parziale (→ predicato decidibile). ...
Leggi Tutto
ricorsivo
agg. [der. di ricorrere]. – In matematica e in logica matematica, sinon. di ricorrente (nel sign. 3 c); in partic., nella teoria della ricorsività, funzioni r. primitive, quelle che si possono ottenere dalle funzioni iniziali mediante...
piazza
s. f. [lat. platĕa «via larga, piazza» (dal gr. πλατεῖα, propriam. femm. di πλατύς «largo»); cfr. platea, che risale a una variante lat. platēa con e lunga]. – 1. a. Area libera, più o meno spaziosa, di forma quadrata, rettangolare,...