problema dell’arresto
Fabrizio Luccio
Primo esempio di problema indecidibile, cioè che non ammette alcun algoritmo di risoluzione. Il problema dell’arresto nacque nel 1936, sulla base di studi sugli [...] arbitrariamente un algoritmo A e un dato D, stabilire se la computazione A(D) termina in un numero finito di passi. Turing dimostrò che non può esistere alcun algoritmo ARR che stabilisca in tempo finito se la computazione A(D) si arresta anch’essa ...
Leggi Tutto
Böhm, Corrado. – Matematico e informatico italiano (Milano 1923 - Roma 2017). Laureatosi nel 1946 in ingegneria elettronica presso il Politecnico di Losanna, ha conseguito il dottorato in matematica al [...] Politecnico di Zurigo nel 1951. Dalle sue ricerche sui linguaggi per la programmazione sulla macchina di Turing è nato, in collaborazione con G. Jacopini, il teorema di Böhm-Jacopini (1966). Tra i suoi contributi più importanti vi è il cosiddetto ...
Leggi Tutto
Rispetto a tutto ciò che la c. prometteva negli anni Quaranta e Cinquanta, gli sviluppi realizzati in seguito da questa nuova scienza risultano in parte superiori e in parte inferiori all'aspettativa.
I [...] al 1948 sono da attribuire in parte al loro carattere eccessivamente interdisciplinare. Solo studiosi eccezionali, come A. M. Turing, J. von Neumann e N. Wiener, nel frattempo scomparsi, potrebbero infatti abbracciare dall'alto di un completo dominio ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] Stearns e Philip M. Lewis, i quali hanno definito e studiato il concetto di classe di complessità per le macchine di Turing. A tali studi hanno fatto seguito quelli di Manuel Blum e Albert Meyer, aventi per oggetto le proprietà astratte (indipendenti ...
Leggi Tutto
intelligènza artificiale (IA) Disciplina che studia se e in che modo si possano riprodurre i processi mentali più complessi mediante l'uso di un computer. Tale ricerca si sviluppa secondo due percorsi [...] sempre più efficienti. Fino a oggi, però, nessun calcolatore è mai riuscito a superare il test di Turing (che prende il nome dal logico A.M. Turing che lo ideò) che afferma che una macchina 'pensa' quando un osservatore umano che interagisca con essa ...
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 [...] e cambiare lo stato interno. Benché nella pratica questo modo di operare fosse poco efficiente, esso realizzava gli obiettivi di Turing. Nel 1936 egli mostrò che la sua macchina era in grado di eseguire qualsiasi calcolo matematico, ma non era capace ...
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 [...] e cambiare lo stato interno. Benché nella pratica questo modo di operare fosse poco efficiente, esso realizzava gli obiettivi di Turing. Nel 1936 egli mostrò che la sua macchina era in grado di eseguire qualsiasi calcolo matematico, ma non era capace ...
Leggi Tutto
LOGICA E INFORMATICA
Carlo Cellucci
I. McCarthy (1963) afferma che è ragionevole sperare che le relazioni tra l'i. e la l. matematica nel prossimo secolo saranno altrettanto fruttuose di quelle tra [...] mediante un numero finito di operazioni. Tale convinzione venne confutata da un risultato di A. Turing (1937). Per ottenere tale risultato Turing ideò un modello puramente matematico dei procedimenti di computo sotto forma di una macchina ideale ...
Leggi Tutto
Scienza cognitiva
Antonio Rainone
Con la locuzione scienza cognitiva, dalla fine degli anni Settanta, si è soliti designare l'insieme delle discipline che hanno per oggetto lo studio dei processi cognitivi [...] . 18-24 (trad. it. in La filosofia degli automi, a cura di V. Somenzi, R. Cordeschi, Torino 1994², pp. 78-85).
A. Turing, Computing machinery and intelligence, in Mind, 1950, pp. 433-60 (trad. it. in La filosofia degli automi, a cura di V. Somenzi, R ...
Leggi Tutto
(o computer, o elaboratore elettronico) Apparecchio o dispositivo utilizzato per l’elaborazione di dati e segnali.
Cenni storici
Le origini
Il desiderio di realizzare uno strumento in grado di compiere [...] E.L. Post, i quali in modo indipendente introdussero nel 1936 due modelli concettuali di elaborazione: la macchina di Turing e il sistema di Post.
I prototipi
I c. progettati e prodotti tra il 1936 e il 1950 erano essenzialmente prototipi, costruiti ...
Leggi Tutto
turingiano
agg. e s. m. [dal nome della regione della Turingia (v. turingio)]. – Piano geologico superiore del permiano, tipico dell’Europa centro-orientale e in partic. della Turingia (corrispondente alla facies detta in Germania Zechstein),...
turingio
turìngio agg. [der. del nome della regione] (pl. f. -ge o -gie). – Della Turingia (ted. Thüringen), regione storica e moderna della Germania centro-orientale: le antiche popolazioni t., di stirpe germanica (e, sost., i turingi); il...