Chi è così bravo da sapermi spiegare il teorema di Godel e le sue conseguenze in relazione alla macchina di Turing? Ma, e qui è il difficile, senza ricorrere alla matematica, ma al massimo ai "soldoni"??

Hai provato su wikipedia? Mi sembra abbastanza accessibile...

dopo gli do un'occhiata.
il fatto è che, per me, queste questioni hanno il fascino di un ortica, quindi sono un pò restio a investire attenzione e cura nel manipolare questi argomenti per capirli. Preferirei che uno bim-bum-bam! me li mostra intuitivamente.
comunque dopo proverò a mettermi di impegno, grazie!

ciao rubin

Goedel dimostra che ogni sistema formale abbastanza potente non è completo, cioè ci saranno infinite proposizioni formali che sulle quali non sapremo decidere - grazie al sistema formale stesso - se sono vere o false.

Indipendentemente Turing scopre un'applicazione del teorema di goedel, e cioè che vi sono un'infinità di problemi irrisolvibili - in linea di principio - da qualsiasi calcolatore (costruibile o immaginario). Non so se sai che ci sono vari infiniti, uno più 'grande' dell'altro; bene, i problemi risolvibili sono in una infinità numerabile (aleph 0, cioè il primo grado di infinito), mentre i problemi irrisolvibili sono in un'infinità non numerabile, diciamo reale o continua (aleph 1), quindi enormemente di più.

Turing ha così delimitato (cioè creato) la scienza informatica, mostrando (in altri contesti) cosa un computer può fare e (che è quello che tu chiedevi) cosa non può fare.


epicurus

ti ringrazio molto, epicurus. questa spiegazione è più che sufficiente al mio caso.
Grazie, ciao

de nada