problemadell’arresto
Fabrizio Luccio
Primo esempio di problema indecidibile, cioè che non ammette alcun algoritmo di risoluzione. Il problemadell’arresto nacque nel 1936, sulla base di studi sugli [...] formalizzazione dei modelli primitivi di calcolo sviluppati all’inizio di quel secolo, tra cui la macchina dello stesso autore. In modo informale il problema può essere così formulato: presi arbitrariamente un algoritmo A e un dato D, stabilire se la ...
Leggi Tutto
Calcolatori
GGianfranco Bilardi e Raffaele Tripiccione
Nicola Cabibbo
Mario Rasetti
Hardware, di Gianfranco Bilardi e Raffaele Tripiccione
Calcolatori paralleli, di Nicola Cabibbo
Calcolo quantistico, [...] domande e risposte è prestabilito. Per esempio, nel problemadella fattorizzazione in aritmetica, la domanda codifica (ad esempio, la semantica del programma e si evita di dover fermare il flusso attraverso la pipeline. Questo riordinamento può essere ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1951-1960
1951-1960
1951
Sui gruppi di omotopia e di omologia. In una serie di articoli (Homologie singulière des espaces fibrés) Jean-Pierre Serre fornisce [...] stabilire se esistano insiemi ricorsivamente enumerabili che non siano né ricorsivi né costruttivamente equivalenti al problemadellafermatadelle macchine di Turing. Nel 1956 uno studente americano, Richard Friedberg, e uno studente russo, Andrei ...
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 [...] matematico, ma non era capace di portarli tutti a termine. In particolare, la macchina di Turing non poteva risolvere il problemadellafermata halting-problem: dato un programma, questo si fermerà per ogni suo input? Ciò rispondeva all'ultima ...
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 [...] di Church interpreta dunque come umanamente impossibili da risolvere. Il più famoso di tali esempi è il cosiddetto 'problemadellafermata': decidere se una data funzione ricorsiva parziale è definita per un dato argomento o, equivalentemente, se un ...
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 dato un generico input per essa, consenta di stabilire se la macchina con quell’input termina il calcolo oppure no. Il problemadellafermata è dunque l’esempio più celebre di funzione non calcolabile. Si può definire la funzione
h = [f|per tutti i ...
Leggi Tutto
teoremi di indecidibilità
Silvio Bozzi
In logica matematica, risultati che affermano che una data teoria formalizzata T non è decidibile, vale a dire non ammette un algoritmo in grado di stabilire in [...] di indecidibilità che non riguardano direttamente teorie formalizzate, per es., il problemadellafermata per macchine di Turing, il problemadella lambda-convertibilità o quello della derivabilità di parole entro sistemi di Post e così via. Di ...
Leggi Tutto
STRUTTURA
Natale Gucci
Mario Como
Roberto Capra
Paolo Zellini
(App. II, II, p. 923; III, II, p. 857; IV, III, p. 504)
Ingegneria civile. Strutture di acciaio. - Le più recenti applicazioni delle [...] , e si erano scoperti, su questa linea, diversi risultati di indecidibilità: per es. Turing dimostrò che il ''problemadellafermata'' è indecidibile, cioè non esiste una procedura di calcolo che decida, per ogni programma, se questo avrà termine ...
Leggi Tutto
Informazione e computazione quantistica: teoria
Mario Rasetti
Al crocevia tra scienza e tecnologia
La nuova disciplina che va sotto il nome di informazione e computazione quantistica si sviluppa al [...] o no, permette alla computazione principale, che l’algoritmo esegue, di diventare efficiente. Turing era interessato al problemadellafermata (halting problem), vale a dire quello di predire a priori per un dato programma di calcolo, semplicemente ...
Leggi Tutto
tempo
tèmpo s. m. [lat. tĕmpus -pŏris, voce d’incerta origine, che aveva solo il sign. cronologico, mentre quello atmosferico (cfr. al n. 8) era significato da tempestas -atis]. – 1. L’intuizione e la rappresentazione della modalità secondo...
stazione
stazióne s. f. (ant. m.: cfr. stazzone) [dal lat. statio -onis «modo di stare; fermata, dimora, riposo», der. di stare «stare, stare fermo, stare ritto»]. – 1. Con riferimento al corpo umano, modo di stare, spec. nella locuz. s. eretta,...