Macchina di Turing: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Etichette: Modifica da mobile Modifica da web per mobile |
Etichette: Modifica da mobile Modifica da web per mobile |
||
Riga 14:
=== Caratteristiche ===
Nel [[1936]] venne pubblicato un articolo di [[Alan Turing|Alan Mathison Turing]] intitolato ''On computable numbers, with an application to the [[Entscheidungsproblem]]'', in cui l'autore risolveva negativamente l'[[Entscheidungsproblem]] (o problema della decidibilità), lanciato nel [[1900]] da [[David Hilbert]] e [[Wilhelm Ackermann]]. La questione era stata posta da Hilbert nei seguenti termini: «esiste sempre, almeno in linea di principio, un metodo meccanico (cioè una maniera rigorosa) attraverso cui, dato un qualsiasi enunciato matematico, si possa stabilire se esso sia vero o falso?»
I vantaggi derivanti dal possedere un tale metodo sono enormi e meritano tutta l'enfasi che [[David Hilbert|Hilbert]] e molti altri al suo seguito diedero alla questione: un tale algoritmo sarebbe in grado di risolvere tutti i problemi matematici e, molto di più, sarebbe possibile ridurre ogni ragionamento umano a mero calcolo meccanizzabile. Una prima forte risposta la diede il matematico boemo [[Kurt Gödel|Gödel]] in occasione della seconda conferenza sull'[[epistemologia]] delle scienze esatte di [[Königsberg]] (1930), in cui espresse per la prima volta pubblicamente le idee racchiuse nel suo più celebre lavoro sull'incompletezza dei sistemi formali coerenti ([[Teoremi di incompletezza di Gödel|primo teorema di incompletezza]]); Gödel dimostrò che la semplice coerenza di un [[sistema formale]] non può garantire che ciò che in esso viene dimostrato sia vero oppure falso. Il sogno di [[David Hilbert|Hilbert]] stava già sfumando, quando Turing pubblicò il suo articolo, in cui dimostrò l'insolubilità dell'Entscheidungsproblem.
| |||