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
lògica matemàtica Branca della logica, che utilizza un linguaggio simbolico e adotta un sistema di calcolo di tipo algebrico per esaminare le espressioni di un discorso deduttivo. Queste ultime possono [...] , e così via). Sullo sfondo, vi sono le indagini legate alla teoria degli insiemi e a quella della ricorsività, che tematizzano in generale le nozioni collegate alla costruzione di strutture astratte e alla definizione di procedure combinatorie. Di ...
Leggi Tutto
Modelli, Teoria dei
Silvio Bozzi
Malgrado le modeste origini che ne hanno segnato la nascita, la teoria dei modelli ha sviluppato nel corso del tempo idee e metodi che l'hanno resa uno dei settori più [...] standard dell'aritmetica AP di Peano e il loro studio ‒ che si situa nel terreno di confluenza tra teoria della ricorsività e teoria dei modelli ‒ ha portato a risultati di grande interesse. Tra i primi risultati ottenuti utilizzando i modelli non ...
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à.