Hello world !
Ouh la la, une semaine sans billet ! Rien ne va plus ! Rassurez-vous, je ne suis pas mort, mais juste en train d'approfondir ma connaissance de l'algorithmique et des automates cellulaires...
Parlons donc informatique pour une fois. Comme vous le savez sûrement, il existe des problèmes insolubles informatiquement (indécidables). L'exemple canonique de premier programme que tout un chacun étudie est le fameux "printf("hello, world\n");". Facile de savoir ce que fait cette simple ligne. Pourtant, ils est possible de démontrer qu'il est impossible de fabriquer un programme informatique qui testera à coup sûr si un programme écrira en sortie un "hello, world \n".
Démonstration par l'absurde : supposons qu'un tel programme H existe. Ce programme prend en entrée un programme P, un input d'exécution I de ce programme, et répond "oui" ou "non" selon que le programme affiche en sortie "hello, world\n". Soyons maintenant pervers : remplaçons le "non" en sortie par "hello, world\n". Considérons que I est le programme P lui-même, si bien que P se prend lui-même comme input. Appelons ce nouveau programme H modifié H' : H' renvoie donc ce qui arrive lorsqu'un programme P s'exécute avec son propre code en input, et répond "oui" si P exécuté sur lui-même affiche "hello, world\n" , et "hello, world\n" sinon. Prenons maintenant P=H', et évaluons s'il imprime "hello, world\n" à l'aide H'. Si cette exécution nous répond "oui", cela signifie que H' évalué avec H' comme input affiche "hello, world\n". Absurdité, il ne répond donc pas "oui" ! Maintenant, si H' évalué avec H' en input donne "hello, world\n", et bien la phrase magique est affichée, donc cette exécution doit renvoyer "oui". Deuxième absurdité.
Nous venons donc de démontrer par l'absurde qu'il est impossible de savoir si un programme affiche "hello, world\n" ! Vive l'informatique !
En photo : Alan Turing, père de l'informatique. Il s'est suicidé en mangeant une pomme empoisonnée... brrrrrr.....
Référence : Introduction to Automata Theory, Languages, and Computation, Hopcroft, Motwani, Ullman.
Parlons donc informatique pour une fois. Comme vous le savez sûrement, il existe des problèmes insolubles informatiquement (indécidables). L'exemple canonique de premier programme que tout un chacun étudie est le fameux "printf("hello, world\n");". Facile de savoir ce que fait cette simple ligne. Pourtant, ils est possible de démontrer qu'il est impossible de fabriquer un programme informatique qui testera à coup sûr si un programme écrira en sortie un "hello, world \n".
Démonstration par l'absurde : supposons qu'un tel programme H existe. Ce programme prend en entrée un programme P, un input d'exécution I de ce programme, et répond "oui" ou "non" selon que le programme affiche en sortie "hello, world\n". Soyons maintenant pervers : remplaçons le "non" en sortie par "hello, world\n". Considérons que I est le programme P lui-même, si bien que P se prend lui-même comme input. Appelons ce nouveau programme H modifié H' : H' renvoie donc ce qui arrive lorsqu'un programme P s'exécute avec son propre code en input, et répond "oui" si P exécuté sur lui-même affiche "hello, world\n" , et "hello, world\n" sinon. Prenons maintenant P=H', et évaluons s'il imprime "hello, world\n" à l'aide H'. Si cette exécution nous répond "oui", cela signifie que H' évalué avec H' comme input affiche "hello, world\n". Absurdité, il ne répond donc pas "oui" ! Maintenant, si H' évalué avec H' en input donne "hello, world\n", et bien la phrase magique est affichée, donc cette exécution doit renvoyer "oui". Deuxième absurdité.
Nous venons donc de démontrer par l'absurde qu'il est impossible de savoir si un programme affiche "hello, world\n" ! Vive l'informatique !
En photo : Alan Turing, père de l'informatique. Il s'est suicidé en mangeant une pomme empoisonnée... brrrrrr.....
Référence : Introduction to Automata Theory, Languages, and Computation, Hopcroft, Motwani, Ullman.
3 commentaires:
hello, tom \n
C'est un brin tordu comme probleme, non ? Mais bon, on est un geek ou on ne l'est pas...
G.
Ca c'est bien vrai ! D'ailleurs, je viens de refaire le "geek test", je suis à 3031 ! Total Geek !
Entre parenthèses, je pense que tenir un blog, cela devrait valoir quelques points à ce test... Révolte !
Je suis sur que tu as menti pour augmenter ton score !
G.
Enregistrer un commentaire