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
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
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
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
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
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
ricorsivita
ricorsività s. f. [der. di ricorsivo]. – In matematica e in logica matematica, la proprietà di essere ricorsivo, cioè ricorrente. Teoria della r., teoria matematica che si propone lo studio, nell’ambito dei numeri naturali, di...
binormalita
binormalità s. f. [der. di binormale]. – Nella logica matematica, la condizione di ciò che è binormale, ed è una delle formulazioni equivalenti del concetto generale di ricorsività.