funzione calcolabile
funzione calcolabile funzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di [...] rappresenta in maniera adeguata l’insieme delle funzioni calcolabili nel senso che ogni funzione calcolabile può essere definita come funzionericorsiva e, viceversa, ogni funzionericorsiva è una funzione calcolabile. La tesi di Church è avvalorata ...
Leggi Tutto
funzione definita ricorsivamentefunzione definita ricorsivamentefunzione di dominio N i cui valori sono determinabili attraverso passi successivi di calcolo, tali che, assegnato il suo valore iniziale, [...] e si risolve soltanto quando si raggiunge il passo iniziale. Per esempio:
Una funzione definita ricorsivamente può così essere calcolata tramite un algoritmo ricorsivo (→ calcolo ricorsivo; → funzionericorsiva; → funzionericorsiva primitiva). ...
Leggi Tutto
funzione annullatore
funzione annullatore nella teoria delle funzioniricorsive, funzione aritmetica che associa a ogni numero naturale il numero 0; è spesso indicata simbolicamente come Z(x) e si ha: [...] ∀x ∈ N, Z(x) = 0 (→ funzionericorsiva). ...
Leggi Tutto
Matematico e logico-matematico statunitense (Washington 1903 - Hudson, Ohio, 1995), prof. di matematica (1947-61), poi di matematica e filosofia (1961-67) a Princeton, dal 1967 di matematica e filosofia [...] di Post. La tesi di Ch. e l'affermazione inversa (cioè ogni funzionericorsiva è effettivamente calcolabile) precisano la nozione di procedimento effettivo di calcolo nel caso di funzioni di numeri naturali. La tesi di Ch. non si può né dimostrare ...
Leggi Tutto
ricorsività La proprietà di essere ricorsivo, cioè ricorrente. Teoria della r., o della ricorsione, o computabilità, la disciplina che si occupa di fornire una caratterizzazione matematica del concetto [...] iniziali mediante un numero finito di applicazioni delle regole di sostituzione e di induzione. Esempi di funzioniricorsive primitive sono le comuni funzioni aritmetiche elementari: predecessore di x: pr(1) = 0, pr(x′) = x; segno di x: sg(0) = 0 ...
Leggi Tutto
Matematica
Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo [...] concetto di operazione effettiva (realizzabile cioè mediante a.). Su questa linea si sviluppano il concetto di funzionericorsiva, la definizione delle funzioni mediante l’operatore di astrazione lambda e i sistemi di combinatori di H.B. Curry. Dall ...
Leggi Tutto
Logico e matematico statunitense (Augustów, Polonia, 1897 - New York 1954); prof. (1944) all'univ. di New York. Nel 1921 diede la prima dimostrazione della completezza sintattica del calcolo proposizionale [...] . Importante la sua teoria dei sistemi formali e degli insiemi ricorsivamente numerabili, di quegli insiemi, cioè, che o sono vuoti o sono codominî di una funzionericorsiva. Nel 1947 dimostrò l'impossibilità di risolvere il problema della ...
Leggi Tutto
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] , è possibile garantire l'applicabilità del teorema del punto fisso di Knaster-Tarski e individuare le funzioni calcolate da programmi ricorsivi come i punti fissi associati a tali programmi.
L'approccio denotazionale ha il pregio di una notevole ...
Leggi Tutto
Logica matematica
Abraham Robinson
*La voce enciclopedica Logica matematica è stata ripubblicata da Treccani Libri, arricchita e aggiornata da un’introduzione di Gabriele Lolli e un saggio di Beppo [...] due regole di derivazione. Sia f0(x), f1(x), f2(x), ... la successione di funzioniricorsive ottenute in tal modo. Si consideri la funzione F(x)=fx(x)+1. Questa funzione è computabile in senso intuitivo, dal momento che, fissato un numero naturale n ...
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,...