Newsgroup: it.scienza.informatica
Titolo: Teorema corretezza programma ?

Salve a tutti e spero di non essere OT: 
esiste un teorema che dimostri l'impossibilità di scrivere un
programma senza errori (le leggi di murpy non valgono ;)?
è da ieri che penso dove posso averlo visto e ho ripreso in mano
alcuni testi però non ho trovato nulla, ma sono quasi convinto della
sua esistenza .... 
P.S. se esiste sollo nella mia mente lo enuncio io e lo dimostro per
induzione :-))) e divento famoso e celebre in tutto il mondo!! 

 programma senza errori (le leggi di murpy non valgono ;)?
#include <stdio.h>
void main() {
    	printf("No, perche' sarebbe sbagliato: programmi senza errori se ne 
possono scrivere senza problemi. :-)\n");
}
-- 
Life's something u don't get out alive..
ObjectZone - 
http://space.tin.it/computer/csadun


wrote:

Trovato!!! ho avuto un po di tempo mi ricordavo male io e di
conseguenza mi sono espresso in modo sbagliato era il teorema di Gödel
ripreso da Turing: 
ecco un'url molto interessante da cui partire a chi interessa
approfondire l'argomento
http://www.vialattea.net/odifreddi/godel.htm
<quote>
Consideriamo un computer programmabile ed il suo problema della
fermata, che chiede se il computer si ferma o no quando lavora con un
dato programma p ed un dato input i. Il problema della fermata non può
essere decidibile, cioè risolubile dal computer stesso mediante un
programma P . Altrimenti esisterebbe un altro programma P1 che lavora
come segue, dato il programma p: si usa P per decidere se il programma
p si ferma sull'input p o no, e poi si fa fare a P1 il contrario.
Quindi P1 si ferma su p se e solo se p non si ferma su p, ed in
particolare P1 si ferma su P1 se e solo se P1 non si ferma su P1,
contraddizione.
Il teorema di Turing si può quindi formulare dicendo che un computer
programmabile è incompleto, nel senso che non può decidere tutti i
problemi riguardo al proprio funzionamento. Più in particolare, benché
un computer programmabile possa simulare passo per passo qualunque
programma su qualunque input (localmente), non può decidere in
generale se tali simulazioni porteranno o no ad un risultato
(globalmente)
</quote>
Ciao Luca

 }
:-)))))
Ciao Cristiano, dai tempi di ICA non ci si vede piu'...
Leggi sotto... scherzo... scherzo!  ;-)
[glucasole@server glucasole]$ vi errore.c
[glucasole@server glucasole]$ cat errore.c
#include <stdio.h>
void main() {
        printf("No, perche' sarebbe sbagliato: programmi senza errori se ne
possono scrivere senza problemi. :-)\n");
}
[glucasole@server glucasole]$ gcc errore.c
errore.c: In function `main':
errore.c:3: warning: return type of `main' is not `int'
[glucasole@server glucasole]$ vi errore.c
[glucasole@server glucasole]$ cat errore.c
#include <stdio.h>
main() {
        printf("No, perche' sarebbe sbagliato: programmi senza errori se ne
possono scrivere senza problemi. :-)\n");
}
[glucasole@server glucasole]$ gcc errore.c
[glucasole@server glucasole]$ ./a.out
No, perche' sarebbe sbagliato: programmi senza errori se ne
possono scrivere senza problemi. :-)
[glucasole@server glucasole]$ :-)
bash: syntax error near unexpected token `:-)'
[glucasole@server glucasole]$  :-)))))
bye G.L.

 errore.c:3: warning: return type of `main' is not `int'
Devi usare un compilatore C++. ;-)


 ripreso da Turing:
Questo e' qualcosa di completamente diverso: l'halting problem e' uno
degli esempi per cui si deduce che non tutte le funzioni (ovvero, i
problemi) pensabili sono computabili. 
Vale di solito la pena notare che, anche in quel caso, il significato non
e' che non si possa dire *mai* se un programma termina o meno (Helloworld
termina senza problemi, e lo si puo' verificare via un altro programma
;-) - ma che non si puo' scrivere un programma che faccia tale verifica
per *tutti* i programmi. 


programmabile è incompleto, nel senso che non può decidere tutti i
Appunto, questo non e` un teorema di (in)correttezza, ma di incompletezza.
In soldoni:
	- Godel dimostra che esistono teoremi indimostrabili
	- Turing che non esistono procedure per decidere se un teorema e`
	  dimostrabile.
In sostanza ci sono dei problemi (ALCUNI, non tutti) che un calcolatore
non puo` computare in un tempo finito.
Es: le serie di Goodstein, il problema della fermata, la decidibilita`, 
ecc...
Ma questo non vuol dire che non si possa scrivere un programma senza
errori. Pensa al programma che non fa nessuna operazione...
Oppure pensa a qualunque programma. Esso compie ESATTAMENTE le
operazione codificate senza nessun errore (eccettuati quelli dovuti 
a difetti fisici del calcolatore). Se poi queste operazioni sono
quelle che intendeva il programmatore non si puo` sapere. :-)

 Devi usare un compilatore C++. ;-)
In C++ "void main()" è un errore. CHe poi molti compilatori lo accettino
è anche vero. Ma non sono conformi allo standard. Non ricordo cosa dica
il C ma per il C++ deve essere "error", non "warning".
--
Andrea Ferro
IHHC - Member of HT-Group  DVD Authoring operator  Fan of I.Asimov
C++ Master: 
http://www.brainbench.com/transcript.jsp?pid=2522556
This post expresses personal opinions which may or may not be the
opinions of the company(s) I work for. I speak for myself only.

 
Il (gcc) C da warning... e` anche vero che un programma che termina su 
piattaforma
dos/win non ha valore di uscita. (Non viene neanche notificato al padre la 
terminazione
mi pare)

 
Basta togliere qualche costrutto superfluo al linguaggio e si puo` fare
(ad esempio il while :-) )
Giorgio

 il C ma per il C++ deve essere "error", non "warning".
E' vero - ma la domanda non era sullo standard C++. ;-)


 mi pare)
Falso. Sia in DOS che in Windows i programmi hanno valore di uscita. E
questo può essere utilizzato da un eventuale processo "padre".
Ma se anche non fosse così, lo standard C++ dice che "void main()" è un
errore (ripeto: non leggo e non seguo il C da oltre 8 anni e non ricordo
cosa dica quello standard, e non ho mai letto il nuovo standard C. Ma
per il C++ sono sicuro).


 E' vero - ma la domanda non era sullo standard C++. ;-)
No. Ma tu postavi il codice come programma corretto. Sul momento pensavo
io stesso di risponderti che non lo era. Poi ho pensato che
probabilmente lo intendevi come codice C e non come codice C++. Come
codice C++ quel programma non è corretto (se il compilatore è conforme
non te lo compila). Se è C ... non ricordo.
Qualcuno ti dice che il compilatore C gli da errore e tu gli rispondi
che deve usare un compilatore C++. Solo a questo punto intervengo. Se
usa un compilatore C++ ottiene certamente un errore di compilazione (a
meno che il compilatore sia vecchio e non conforme, ma allora è
discutibile il fatto che compili il C++, dato che il C++ è un linguaggio
ben definito e standardizzato).
Quindi se il tuo codice è corretto, allora NON è codice C++. Forse è
corretto come codice C (non ne sono sicuro). Ma sicuramente non è C++
corretto.


 No. Ma tu postavi il codice come programma corretto.
No, postavo un programma che gira senza errori.. lo compili (con gcc, per 
esempio), lo esegui e funziona senza errori. Ma hai capito che era un 
battuta? Non e' che la domanda fosse esattamente posta in termini tecnici 
(mio dio, il senso dell'umorismo dov'e' finito? :-)
Ah, la risposta giusta al remark di Gianluca era, effettivamente - "e' solo 
un warning" ;-)


 che deve usare un compilatore C++.
Non capisco una cippa di C++, e pochissimo di linguaggio C. Ho copiato ed
incollato dentro una sessione telnet, penso che l'impulso sia stato dato dal
fatto che sul momento lo spirito di murphy si dev'essere impossessato della
mia mente... :-)))), dopodiche' ho pensato di postare per scherzo
(realizzando un notevole OT, infatti non so se anche questo post
passera')    ;-)
Certo che, giuro non so spiegarmi il perche', quella void davanti al main mi
dava un sentore di cosa sospetta...
Ma gcc non e' un compilatore C++? Senno', come mi compilerebbe programmi per
X? (supponga che sia dura fare programmi per X in C puro...)
bye G.L.

Gian Luca Sole wrote:

sarebbe:
gcc e` C
g++ e` C++
poi a dire il vero sono la stessa cosa, dipende se compila un .c o un .C
cambia qualche impostazione di default ...
No, fare programmi X in C o C++ veramente non fa molta differenza visto che
si richiamano le stesse funzioni di libreria...
o meglio non ci sono oggetti nel toolkit base...
Giorgio

quelle che intendeva il programmatore non si puo` sapere. :-)
comunque secondo me si può dimostrare per induzione che un qualsiasi
programma compilato superiore alle N righe compie  delle operazioni
che non erano previste .... (possono essere features o bug dipende dai
punti di vista:-) 
Ciao Luca

Non mi sembra che questo dimostri che non si puo' scrivere un programma
senza errori....
Fondamentalmente si dimostra che non si puo' dire se un programma e'
corretto (che termini correttamente con tutti gli input possibili) o meno...
che e' un po' diverso: il fatto di non poter dimostrare che una cosa sia
corretta o meno non implica che sia impossibile che sia corretta...
Boia, che geniaccio Turing!!!

 punti di vista:-) 
impossibile dimostrarlo, tanto meno per induzione. Puoi pero' dire
che e' statisticamente molto probabile. Ma in tal caso non diresti
nulla di nuovo rispetto a quello che i programmatori sanno gia' fin
dalla notte dei tempi (informatici) :)
-- 
addio, e grazie per tutto il pesce

 X? (supponga che sia dura fare programmi per X in C puro...)
no, gcc e' un compilatore C e basta. g++ invece e' un compilatore C++.
Che poi abbiano il "cuore" in comune e' un'altra cosa :)
Ti compila i programmi per X semplicemente perche' sono programmi C.
C'e' ben poca differenza tra programmare sotto X in C o C++, le
librerie di base sono le stesse. Se poi sei sano di mente :)) ed
usi qualche toolkit come le GTK anziche' X puro, puoi programmare in
decine di linguaggi diversi senza problemi.
Ah, e visto che se ne parlava, lo standard C prevede solo due
prototipi possibili per la funzione main:
int main(void);
int main(int argc, char *argv[]);
in ogni caso deve sempre tornare un int :)


no, gcc e' un compilatore C e basta. g++ invece e' un compilatore C++.
No, in origine gcc stava per Gnu C Compiler, adesso sta per Gnu
Compiler Collection poiché comprende altri compilatori (C++,
Fortran...).
-- 
Marco Barisione (ICQ 84277092)

 Ciao Luca
Non credo che sia cosi facile da dimostrare..
considera questo programmino C:
#include <stdio.h>
#define N       1000000000L /* inserire un numero grande a piacere */
int main()
{
        long long i;
        printf ("#include <stdio.h>\n\n");
        printf ("int main()\n");
        printf ("{\n");
        for (i=0 ; i<N ; i++) {
                printf(" printf (\"%ld \\n\");\n", i );
        }
 
        printf("}\n");
}
questo programmino genera un programma superiore alle N righe
che, compilato, scrive i numeri da 0 a N-1, senza compiere
operazioni non previste. 
Beh, in realta' dovrebbe funzionare per N <= 2^63, ma 
credo che programmi con un numero di linee maggiori di 2^63
siano alquanto rari da trovare... :-)
Saluti
Fabio Lopiano