ricorsività

Enciclopedia on line

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 [...] di algoritmo. Teoria della ricorsività La motivazione originaria per lo studio della r. fu soprattutto il problema della decisione per le teorie formali (formulato da E. Schröder nel 1895 e ripreso da L. Löwenheim nel 1915 e D. Hilbert nel 1918), ... Leggi Tutto

CATEGORIA: TEMI GENERALI

TAGS: FUNZIONE RICORSIVA PRIMITIVA – FUNZIONE DI ACKERMANN – FUNZIONI RICORSIVE – TEORIA DEI NUMERI – NUMERI NATURALI

computabilità

Enciclopedia on line

computabilità In logica matematica, nozione che di solito s’identifica con quella di ricorsività generale, introdotta intorno al 1936 da A.M. Turing e da E.L. Post. Una funzione numerica di n variabili [...] si dice computabile se esiste un algoritmo per cui si possa, con un numero finito di passi, calcolare per ogni ennupla di argomenti il valore assunto dalla funzione ... Leggi Tutto

CATEGORIA: LOGICA MATEMATICA

TAGS: LOGICA MATEMATICA – ALGORITMO

minimalizzazione

Enciclopedia on line

Particolare tipo di procedimento, usato in logica matematica e soprattutto nella teoria della ricorsività, nel quale si fa uso dell’operatore di m., o operatore-μ, che consente di definire in modo opportuno [...] una funzione a partire da una funzione data o da un predicato dato. Procedimento e operatore di m. possono essere intuitivamente descritti mediante la formula μxPx che si legge «il più piccolo x tale che ... Leggi Tutto

CATEGORIA: LOGICA MATEMATICA

TAGS: LOGICA MATEMATICA

La seconda rivoluzione scientifica: matematica e logica. Teoria della ricorsività

Storia della Scienza (2004)

La seconda rivoluzione scientifica: matematica e logica. Teoria della ricorsivita Piergiorgio Odifreddi Teoria della ricorsività La teoria della ricorsività affronta lo studio delle funzioni con lo [...] viceversa (e dunque il primo è più facile da risolvere del secondo). Una buona parte dei risultati della teoria della ricorsività consiste nello studio, iniziato da Kleene e Post nel 1954, delle proprietà di struttura dei gradi. Per esempio, è ovvio ... Leggi Tutto

CATEGORIA: STORIA DELLA MATEMATICA

calcolabilita

Dizionario delle Scienze Fisiche (1996)

calcolabilita calcolabilità [Der. di calcolabile] [ALG] Generic., la proprietà di essere calcolabile. ◆ [FAF] Per una teoria, è una delle formulazioni equivalenti del concetto generale di ricorsività, [...] detta anche definibilità e studiata per la prima volta da K. Gödel nel 1936 (Über die Länge von Beweisen): v. Gödel, teorema di: III 56 c ... Leggi Tutto

CATEGORIA: FISICA MATEMATICA – STORIA DELLA FISICA – ALGEBRA – EPISTEMOLOGIA – METAFISICA

Markov, Andrej Andreevič, iunior

Enciclopedia on line

Matematico e logico russo (Pietroburgo 1903 - Mosca 1979), figlio del precedente. Il suo nome è legato agli algoritmi normali o di M., alla computabilità secondo M., che è equivalente alla ricorsività, [...] al principio di normalizzazione o principio di Markov. Questo principio, che corrisponde in termini algoritmici alla tesi di Church, può essere così espresso: "Tutti gli algoritmi in un alfabeto A sono ... Leggi Tutto

CATEGORIA: BIOGRAFIE

TAGS: LOGICA INTUIZIONISTA – RICORSIVITÀ – ALGORITMO – MOSCA

ricorrenza

Dizionario delle Scienze Fisiche (2012)

ricorrenza ricorrènza [Der. di ricorrente] [LSF] Ciascuno dei casi in cui un dato fenomeno si verifica, sinon. di occorrenza. ◆ [ALG] (a) Sinon. di induzione (completa), come nelle locuz. definizione [...] per r., dimostrazione o ragionamento per r., principio di ricorrenza. (b) Sinon. di ricorsività. ◆ [GFS] Metodo della r.: v. terremoto, previsione del: VI 244 a. ◆ [MCS] Tempo di r.: v. oltre: Teorema di ricorrenza. ◆ [MCS] Teorema di r.: in un ... Leggi Tutto

CATEGORIA: FISICA MATEMATICA – GEOFISICA – MECCANICA – MECCANICA DEI FLUIDI – MECCANICA QUANTISTICA – TEMI GENERALI – ALGEBRA – STATISTICA E CALCOLO DELLE PROBABILITA

Odifreddi, Piergiorgio

Enciclopedia on line

Odifreddi, Piergiorgio. -  Matematico e scrittore italiano (n. Cuneo 1950). Laureato in matematica a Torino (1973), ha proseguito gli studi negli Stati Uniti presso le università dell’Illinois e della [...] di matematica all’università di Torino (2001-07). Ha svolto attività di ricerca nel campo della teoria della ricorsività, ed è anche saggista e storico della scienza. Attivo nella divulgazione scientifica, tra le sue pubblicazioni occorre citare ... Leggi Tutto

CATEGORIA: BIOGRAFIE

TAGS: PROVA DEL NOVE – FENOMENOLOGIA – STATI UNITI – KURT GÖDEL – MATEMATICA

computabile

Dizionario delle Scienze Fisiche (1996)

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] [...] , le grandezze che possono essere calcolate con un elaboratore adeguatamente programmato; la teoria della computabilità, o della ricorsività, studia i limiti teorici di un tale procedimento di calcolo. ◆ [INF] Funzione c.: funzione numerica di n ... Leggi Tutto

CATEGORIA: FISICA MATEMATICA – STORIA DELLA FISICA – TEMI GENERALI – ALGEBRA – EPISTEMOLOGIA – METAFISICA

ricorsivo

Dizionario delle Scienze Fisiche (2012)

ricorsivo ricorsivo [agg. Der. di ricorrere: (→ ricorrente)] [LSF] Sinon. di ricorrente. ◆ [ALG] [INF] Algoritmo, o procedimento o procedura, r.: algoritmo che è formulato con esplicito riferimento a [...] Filtro non r.: v. immagini, elaborazione di: III 167 e. ◆ [ALG] [INF] Funzioni r. primitive: nella teoria della ricorsività, quelle che si possono ottenere dalle funzioni iniziali mediante un numero finito di applicazioni delle regole di sostituzione ... Leggi Tutto

CATEGORIA: FISICA MATEMATICA – TEMI GENERALI – ALGEBRA – ELETTRONICA