funzioni ricorsive
Mauro Cappelli
Classe delle funzioni computabili o algoritmiche, ossia delle funzioni n-arie f tali che esiste un algoritmo per computare il valore f(x1,...,x{[) per ogni n-pla di [...] che tutte le funzioni intuitivamente computabili sono ricorsive generali. Accolta questa tesi, risulta precisato il concetto intuitivo di computabilità e, conseguentemente, quello di decidibilità e di costruibilità.
→ Programmazione, algoritmi di ...
Leggi Tutto
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 [...] , New York 1974; W.S. Brainerd, L. H. Landweber, Theory of computation, ivi 1974; Hermes, Enumerabilità decidibilità computabilità, Torino 1975; V. P. Preparata, R. T. Yeh, Introduzione alle strutture discrete, ivi 1976.
Informatica matematica ...
Leggi Tutto
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] dimostrò che la teoria degli interi con + come unico operatore è decidibile. Büchi ottenne negli anni Sessanta la decidibilità di un'altra porzione della logica: la teoria monadica del secondo ordine degli interi con successore. La dimostrazione si ...
Leggi Tutto
Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] dimostrò che la teoria degli interi con + come unico operatore è decidibile. Büchi dimostrò negli anni Sessanta la decidibilità di un'altra porzione della logica: la teoria monadica del secondo ordine degli interi con successore. La dimostrazione si ...
Leggi Tutto
Computer science
Scott Kirkpatrick
La computer science si colloca con caratteristiche peculiari tra le scienze cosiddette esatte e l’ingegneria, costituendo dal punto di vista accademico un settore [...] all’ultima della famosa serie di domande poste da David Hilbert nel 1928 a proposito della completezza, coerenza e decidibilità della matematica formale.
Turing sarebbe diventato la figura principale nello sforzo britannico, coronato da successo, di ...
Leggi Tutto
La grande scienza. Computer science
Scott Kirkpatrick
Computer science
La computer science si colloca con caratteristiche peculiari tra le scienze cosiddette esatte e dell'ingegneria, costituendo dal [...] all'ultima della famosa serie di domande poste da David Hilbert nel 1928 a proposito della completezza, coerenza e decidibilità della matematica formale.
Turing sarebbe diventato la figura principale nello sforzo britannico, coronato da successo, di ...
Leggi Tutto
La seconda rivoluzione scientifica: fisica e chimica (1920-1945). L'elettronica e il calcolo
Jon Agar
L'elettronica e il calcolo
L'elettronica
Nel secondo decennio del XX sec., il termine 'elettronico' [...] Bombe.
Prima della guerra Turing aveva proposto una soluzione al problema presentato da David Hilbert (1862-1943) sulla decidibilità della matematica (in breve Hilbert aveva posto la questione se esisteva una procedura che potesse dare come risposta ...
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 [...] '. Ma con ciò siamo anche pervenuti ad uno dei problemi fondamentali della matematica: il cosiddetto problema della decidibilità o della decisione (Gödel). La nozione metamatematica di costruttività porta al problema di trovare un procedimento che ...
Leggi Tutto
decidibilita
decidibilità s. f. [der. di decidibile]. – La qualità o la condizione di essere decidibile, sia in senso generico, sia nel sign. specifico della logica matematica.