INFORMATICA
Paolo Ercoli
Alberto Marini
Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni [...] T-computabili coincidono con altre due classi di funzioni proposte come totalità delle funzionicalcolabili, cioè con le funzioni definibili con il cosiddetto "λ-calcolo" di A. Church e con le funzioni generali ricorsive di K. Gödel. In ogni caso ...
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 [...] ottenuto g(k1, ..., km)=n. Abbiamo visto che gli schemi che conducono alle funzioni ricorsive primitive sono troppo restrittivi per comprendere tutte le funzionicalcolabili. Ma il metodo impiegato per stabilire questo fatto sarebbe egualmente valido ...
Leggi Tutto
Cibernetica
Ernest H. Hutten
di Ernest H. Hutten
Cibernetica
sommario: 1. Introduzione storica. 2. L'epistemologia delle macchine. 3. La struttura informativa delle macchine. 4. Sistema, processo, informazione [...] lungo è equivalente alla macchina universale di Turing; e quindi tutti i risultati che si riferiscono alle classi di funzionicalcolabili e alla non risolubilità si possono applicare alle macchine reali. Così, i vari programmi ideati per simulare l ...
Leggi Tutto
Computazione, teoria della
Fabrizio Luccio
La necessità del calcolo, pur riconosciuta dall'uomo in tutte le epoche storiche, ha condotto solo in tempi relativamente recenti a una sistemazione teorica [...] di numeri naturali, la risoluzione di P corrisponde al calcolo di una funzione da ℕ su {0,1}: problemi decidibili o indecidibili corrispondono allora a funzionicalcolabili o non calcolabili.
Le MT sono definite come collezione di entità finite ...
Leggi Tutto
Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] possibili a ogni passo. Se quindi il non determinismo non amplia la classe delle funzionicalcolabili, esso incide in modo cruciale sul tempo di calcolo, poiché una sequenza di n passi non deterministici ciascuno dei quali preveda m alternative ...
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 [...] Cantor (1845-1918).
Nei primi anni Trenta ci si cominciò a chiedere quale fosse allora la classe delle funzionicalcolabili. Alonzo Church, Kurt Gödel, Emil L. Post, Alfred Tarski e Alan M. Turing proposero diverse possibili definizioni. Ciascuna ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Giorgio Strano
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
Negli anni Trenta del Novecento i logici riescono a dare uno statuto matematico alla [...] e originale lascito intellettuale della logica novecentesca. Gli anni Trenta sono cruciali per chiarire la nozione di funzionecalcolabile e di procedura finita, e, in generale, per gettare le basi della teoria matematica della calcolabilità, molto ...
Leggi Tutto
funzionecalcolabilefunzionecalcolabilefunzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di [...] a ogni coppia di numeri interi positivi x e y il loro rapporto x : y non è quindi una funzionecalcolabile, bensì semicalcolabile, perché la procedura di calcolo che la definisce è finita in alcuni casi e non lo è in altri. Nel caso della divisione è ...
Leggi Tutto
funzione ricorsiva
funzione ricorsiva in logica, funzione aritmetica, cioè di dominio e codominio N, definita a partire da alcune funzioni base e attraverso alcune regole costruttive che ne garantiscono [...] . La loro importanza è notevole proprio perché l’insieme delle funzioni ricorsive coincide con quello delle → funzionicalcolabili (è questo il contenuto della cosiddetta tesi di → Church). Le funzioni iniziali o di base da cui si parte sono:
• la ...
Leggi Tutto
Church, Alonzo
Logico e matematico statunitense (Washington 1903 - Hudson, Ohio, 1995). Prof. di matematica (1947-61), poi di matematica e filosofia (1961-67) a Princeton, insegnò dal 1967 matematica [...] oggi chiamata tesi di Ch., secondo cui ogni funzione effettivamente calcolabile è ricorsiva. L’evidenza della tesi deriva dal fatto che altre classi di funzionicalcolabili (funzione λ-definibile, funzionecalcolabile da una macchina di Turing, da un ...
Leggi Tutto
calcolatrice
s. f. e agg. [der. di calcolare]. – Macchina da calcolo di non grandi dimensioni che permette di eseguire addizioni e sottrazioni (addizionatrice) ed eventualmente operazioni più complesse come moltiplicazioni, divisioni, estrazioni...
funzione
funzióne s. f. [dal lat. functio -onis, der. di fungi «adempiere»]. – 1. Attività svolta abitualmente o temporaneamente in vista di un determinato fine, per lo più considerata nel complesso di un sistema sociale, burocratico, ecc....