Radjaïdjah Blog

Mot-clé - logique

Fil des billets - Fil des commentaires

mercredi 21 septembre 2016

Enigmatron

Il y a beaucoup de sites dont le but est de réaliser un parcours en résolvant des énigmes ou défis. Ouverture Facile en est un exemple pionnier, avec des énigmes en flash. De même Notpron, en anglais, est connu pour sa difficulté, avec seulement 0,0001% des joueurs qui ont fini les 140 niveaux.

Enigmatron est un autre site de ce genre made in Switzerland, où la plupart des énigmes sont de nature ludique et/ou scientifique (maths, logique, informatique, cryptographie...) et où une certaine capacité à faire des recherches pertinentes sur internet est requise.

Enigmatron

Parfois il est utile d'essayer de se mettre à la place du créateur des énigmes pour comprendre le raisonnement sous-jacent à un problème.

Si vous êtes perdus face à une énigme, il y a un système d'indices pour vous aider, un forum, et il est même possible de demander de l'aide en commentaire sur cet article.

lundi 30 novembre 2015

Escape games IRL

Au départ, le jeu d'exploration point & click, à la Myst.

Le passage en mode confiné a donné naissance aux jeux d'évasion, les escape rooms ou escape games.

De très nombreux escape games existent, en voici une sélection spéciale :

0) Un des plus plus anciens escape games :

  • Crimson Room (la chambre cramoisie) par Toshimitsu Takagi (2004).

1) Les jeux du japonais Kotorinosu sont le nec plus ultra du genre :

2) Les jeux du japonais Neutral ne sont pas en reste :

Il existe des walkthroughs (solutions) mais résoudre le jeu sans aide apporte beaucoup plus de satisfaction.

De la même façon que l'art inspire la nature, le jeu vidéo inspire la vie réelle. En Hongrie, patrie de Ernö Rubik, de Erdös, de von Neumann, ont été conçus les premières escape rooms physiques. Aujourd'hui dans une ville comme Budapest il en existe plus de cinquante.

Si maintenant vous souhaitez construire votre propre escape room, n'hésitez pas à lire les recommandations de Scott Nicholson, prof en escape rooms (!), ou à le voir en vidéo.

mardi 25 août 2015

10 raisons de zapper Windows 10

Alors que c'est le 20e anniversaire de Windows 95, le temps des inquiétudes pour la vie privée dues à la présence d'un GUID (Globally Unique IDentifier) dans les documents produits par Microsoft Word est loin dernière nous.

La dernière version du système d'exploitation de Microsoft, Windows 10, est gratuitement téléchargeable sur le site de Microsoft pour les utilisateurs licenciés des versions récentes. L'entreprise a même sorti une série de 10 petites vidéos intitulée 10 raisons de passer à Windows 10 (10 reasons to upgrade to Windows 10). Ces raisons sont : Windows Store, Continuum, Music and More, Windows Hello, Security, It's Familiar, Cortana, Microsoft Edge, Xbox, Multi-doing.

Derrière ce strass et paillettes de fonctionnalités, la réalité est plus sombre, puisque Windows 10 atteint des sommets de non-respect de la vie privée. Voici 10 bonnes raisons de ne pas adopter Windows 10.

Windows 10

1. La déclaration de confidentialité est claire.

Voici un extrait de la déclaration de confidentialité (version américaine : ''privacy statement'', cf aussi cet article de Numerama) :

Les données que nous recueillons dépendent des services et des fonctionnalités que vous utilisez, et comprennent ce qui suit.

Nom et données de contact. Nous recueillons votre prénom et votre nom de famille, votre adresse email, votre adresse postale, votre numéro de téléphone, et d'autres données de contact similaires.

Identifiants. Nous recueillons les mots de passe, les indices de mot de passe, et des informations de sécurité similaires utilisées pour votre authentification et l'accès à votre compte.

Données démographiques. Nous recueillons des données vous concernant telles que votre âge, votre sexe, votre pays et votre langue préférée.

Centres d'intérêt et favoris. Nous recueillons des données sur vos centres d'intérêt et vos favoris, comme les équipes que vous suivez dans une appli de sport, les stocks que vous suivez dans une appli financière, ou vos villes préférées que vous ajoutez à une appli de météo. En plus de ceux que vous avez explicitement fournis, vos centres d'intérêt et vos favoris peuvent également être devinés ou dérivés d'autres données que nous recueillons.

Données de paiement. Nous recueillons les données nécessaires au traitement de votre paiement si vous faites des achats, comme le numéro de votre moyen de paiement (comme un numéro de carte de crédit), et le code de sécurité associé à votre moyen de paiement.

Données d'utilisation. Nous recueillons des données sur votre manière d'interagir avec nos services. Cela comprend des données telles que les fonctionnalités que vous utilisez, les articles que vous achetez, les pages web que vous consultez, et les termes de recherche que vous entrez. Cela comprend également des données concernant votre appareil, notamment l'adresse IP, les identifiants de l'appareil, les paramètres de région et de langue, et des données concernant le réseau, le système d'exploitation, le navigateur et d'autres logiciels que vous utilisez pour vous connecter aux services. Et cela comprend également des données concernant les performances des services et tout problème rencontré avec ces services.

Contacts et relations. Nous recueillons des données concernant vos contacts et vos relations si vous utilisez un service Microsoft pour gérer vos contacts, ou pour communiquer ou interagir avec d'autres personnes et organisations.

Données de localisation. Nous recueillons des données concernant votre localisation, qui peuvent être soit précises soit imprécises. Les données de localisation précises peuvent être des données du Système de positionnement global (GPS), ainsi que des données identifiant des antennes-relais à proximité et des bornes Wi-Fi, que nous recueillons lorsque vous activez les services et fonctionnalités basés sur la localisation. Les données de localisation imprécises comprennent, par exemple, une localisation dérivée de votre adresse IP ou des données qui indiquent avec moins de précision où vous vous trouvez, comme avec une ville ou un code postal.

Contenu. Nous recueillons le contenu de vos fichiers et de vos communications au besoin pour vous fournir les services que vous utilisez. Cela comprend : le contenu de vos documents, photos, musiques ou vidéos que vous téléchargez sur un service Microsoft tel que OneDrive. Cela comprend également le contenu des communications que vous envoyez ou recevez en utilisant les services Microsoft, comme :

* la ligne d'objet et le corps d'un email,
* le texte ou autre contenu d'un message instantané,
* l'enregistrement audio et vidéo d'un message vidéo, et
* l'enregistrement audio et la transcription d'un message vocal que vous recevez ou d'un message texte que vous dictez.

En outre, lorsque vous nous contactez, pour une assistance clients par exemple, les conversations téléphoniques ou les sessions de discussion avec nos représentants sont susceptibles d'être surveillées et enregistrées. Si vous entrez dans nos magasins, votre image peut être saisie par nos caméras de sécurité.

2. Par défaut, Windows 10 ne respecte pas la vie privée.

Par défaut (configuration définie lors d'une installation express), la configuration de Windows 10 donne un accès quasi-illimité à vos données à Microsoft.

Par exemple, la synchronisation des données (data syncing) envoie l'historique de navigation,les favoris, les sites ouverts, ainsi que les mots de passe des sites et des réseaux wi-fi, sur les serveurs de Microsoft.

Autre exemple, le logiciel gérant les réseaux sans fil, Wi-Fi Sense, demande par défaut à partager l'accès aux réseaux wi-fi connus avec tous les contacts. Cela dit, Microsoft a pensé à un moyen de protéger un réseau afin d'éviter cela : inclure la chaine "_optout" dans le SSID (ce qui se complique quand on apprend que la façon de ne pas être indexé par les voitures Google scannant les réseaux wi-fi est d'avoir un SSID finissant par la chaine "_nomap").

Il a été beaucoup reproché à Microsoft que ces fonctionnalités soient activées par défaut et non pas activables explicitement (par opt-in). La doctrine sous-jacente se résume ainsi : concernant la transmission de données personnelles, qui ne dit mot consent.

De nombreux sites ont explicité les nombreuses étapes à parcourir pour désactiver (opt-out) les différentes fonctionnalités affectant la vie privée. Cependant...

3. Même après configuration, Windows 10 ne respecte pas la vie privée.

Comme l'explique Swati Khandelwal en vertu d'une analyse de Ars Technica, l'assistante Cortana et le moteur de recherche Bing communiquent des informations privées à la maison-mère Microsoft même lorsqu'ils sont instruits de ne pas le faire.

4. Le consommateur devient le produit.

Windows 10 montre que Microsoft s'est mis à la politique de Google ou de Facebook : proposer des produits gratuits à l'utilisateur, en échange de leurs données personnelles.

Et comme le dit l'adage : si c'est gratuit, vous n'êtes pas le consommateur, mais le produit (voir aussi cette présentation).

5. C'est un logiciel propriétaire.

Windows 10 est un logiciel privateur, dans le sens qu'il ne permet pas d'exercer simultanément les quatre libertés logicielles que sont l'exécution du logiciel pour tout type d'utilisation, l'étude de son code source (et donc l'accès à ce code source), la distribution de copies, ainsi que la modification et donc l'amélioration du code source.

6. Il y a de meilleurs choix.

Les distributions Linux grand public comme Ubuntu ou Mint sont techniquement meilleures que Windows 10. Comme le relève Korben, une parodie de la série microsoftienne a été réalisée : 10 bonnes raisons de passer à Ubuntu 15.04.

7. Microsoft semble partenaire du gouvernement US.

Il y a 16 ans, la découverte d'une clef publique nommée _NSAKEY dans une version de Windows publiée par erreur avec des symboles de debugging ont alimenté bien des spéculations concernant une éventuelle possibilité pour la NSA de distribuer des patchs authentifiés (i.e. munis d'une signature électronique validée par le système Windows), même si Bruce Schneier n'y croyait pas à l'époque.

Cette découverte venait en écho des discours du secrétaire américain de la défense William Cohen qui déclarait début 1999 : Je suis persuadé que Microsoft comprend le lien crucial qui existe entre notre sécurité nationale et la prospérité de notre pays. (I believe that Microsoft does understand the crucial connection between our national security and our national prosperity). Mais bon, hors contexte, cette phrase ne veut pas dire grand chose.

8. Windows est vulnérable aux virus et autres malwares.

Avec diverses attaques en provenance des gouvernements américain (Regin, Stuxnet, Flame), chinois (GhostNet), russe (Red October, Turla (ciblant aussi Linux)), les utilisateurs de Windows sont des cibles privilégiées.

Ce n'est pas The Equation Group (NSA) qui dira le contraire. Utiliser un autre système d'exploitation permet d'atténuer ce type d'attaques.

9. C'est un outil d'espionnage industriel.

L'utilisation de Windows 10 au sein d'une entreprise risque de compromettre ses secrets industriels. Une société a donc intéret à réfléchir si le fait de bénéficier de la cosmétique de Windows 10 compense la divulgation à Microsoft de ses collaborateurs, accomplissements, projets, contrats, partenaires, échéances, négociations, etc.

10. Windows 10 peut compromettre un État.

En Russie, note Silicon Angle, des voix s'élèvent contre toute utilisation officielle de Windows 10 : le député Nikolai Levichev a ainsi écrit une lettre au premier ministre Dmitri Medvedev dans laquelle il souligne la possibilité pour Microsoft d'accéder aux mots de passe, contacts, emails, locations, et autres données des utilisateurs, avec un transfert potentiel des données traitées à des agences gouvernementales américaines, raison pour laquelle il souhaite bannir toute utilisation institutionnelle de Windows 10. Cet appel fait suite à une requête du député communiste Vadim Solovyov au procureur général, ainsi qu'à une plainte du cabinet d'avocat Bubnov & Associés auprès du même procureur, les deux demandes soulignant l'aspect illégal de l'accès aux données des citoyens russes par Microsoft.

Il est difficile de décrire exactement les conséquences de l'utilisation de Windows 10 par un État ou une administration telle que la France. L'utilisation au niveau gouvernemental de ce système d'exploitation octroierait à Microsoft l'accès à un stock gigantesque de données nationales, fiscales, et médicales.

Une bonne raison d'adopter Windows 10 : l'illégalité

S'il s'avère que Windows 10 contrevient à la directive 95/46/CE du Parlement européen et du Conseil, du 24 octobre 1995, relative à la protection des personnes physiques à l'égard du traitement des données à caractère personnel et à la libre circulation de ces données, alors vous pouvez porter plainte contre Microsoft et gagner un peu d'argent. Reste à voir comment les juristes interpreteront l'acceptation de la déclaration de confidentialité.

Conclusion

Si vous n'avez rien à faire de votre vie privée ni de celle de vos amis, passez à Windows 10, sinon, ne le faites pas.

vendredi 14 août 2015

Mutex

Les blancs jouent et gagnent en 2 coups.

mutex.png

Si vous ne trouvez pas rapidement, on ne vous jettera pas la pierre.

Solution Solution

0-0-0 Rf8 Td8#

jeudi 6 août 2015

Une illustration du théorème de Gödel

Les problèmes importants auxquels nous faisons face ne peuvent être résolus au même niveau de pensée que celui qui les a engendrés.

Albert Einstein[1]

Avec l'hypothèse de Riemann et la conjecture de Goldbach, un des problèmes ouverts les plus célèbres en mathématiques est la conjecture de Syracuse, due à Lothar Collatz au début du XXe siècle.

Soit n un nombre entier. On lui applique l'opération suivante : s'il est pair, on le divise par deux, s'il est impair on le multiplie par trois et on lui ajoute un. On réitère successivement ce traitement sur le résultat, générant ainsi la n-ième suite de Syracuse. La 7-ième suite de Syracuse est ainsi 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

La conjecture de Syracuse fait état que chaque suite de Syracuse aboutira tôt ou tard au cycle 4, 2, 1. Mais elle a résisté jusqu'à présent à toute démonstration. Le mathématicien hongrois Paul Erdős a dit à propos de cette hypothèse : « les mathématiques ne sont pas encore prêtes pour de tels problèmes ».

Une autre famille de suites dont les termes peuvent monter très haut avant de redescendre a été inventée par le mathématicien britannique Reuven Goodstein en 1944.

Tout entier n possède une unique décomposition en base b : \(n = \Sigma k_i · b^i\), où \(b\) est la base et les \(k_i\) sont les chiffres ; ainsi en base 2 : \(266 = 2^8 + 2^3 + 2^1\). La n-ième suite faible de Goodstein est définie de la façon suivante : à partir de la représentation binaire de n, qui constitue le premier terme, le second terme est obtenu en incrémentant la base de 1 et en retranchant 1 au résultat. Les termes suivants sont construits de façon analogue, en réécrivant au besoin le terme dans la base en cours (cf \(n_4\) ci-dessous) qui est par la suite incrémentée avant de soustraire 1 du résultat s'il est non nul. Les premiers termes de la 266-ième suite faible de Goodstein sont donc :

\(n_0 = 2^8 + 2^3 + 2^1 = 266\)
\(n_1 = 3^8 + 3^3 + 2 = 6 590\)
\(n_2 = 4^8 + 4^3 + 1 = 65 601\)
\(n_3 = 5^8 + 5^3 = 390 750\)
\(n_4 = 6^8 + 6^3 − 1 = 6^8 + 5 · 6^2 + 5 · 6^1 + 5 = 1 679 831\)
\(n_5 = 7^8 + 5 · 7^2 + 5 · 7^1 + 4 = 5 765 085\)

Bien que les premiers termes croissent rapidement, cette suite est à support fini, c'est-à-dire qu'il existe un rang à partir duquel tous les termes deviennent nuls, et c'est en fait le cas pour toutes les suites faibles de Goodstein. C'est le fait de retrancher 1 à chaque étape qui finit par l'emporter sur l'incrémentation de la base.

Contrairement à la conjecture de Collatz, la convergence des suites faibles de Goodstein est simple à démontrer. Intuitivement, à chaque terme d'une suite peut être associé un polynôme de \(\mathbb{N}[X]\) dont les coefficients sont les chiffres de la représentation du terme. Ainsi pour la 266-ème suite de Goodstein, la suite de polynômes est :

\(P_0 = X^8 + X^3 + X^1\)
\(P_1 = X^8 + X^3 + 2\)
\(P_2 = X^8 + X^3 + 1\)
\(P_3 = X^8 + X^3\)
\(P_4 = X^8 + 5 · X^2 + 5 · X^1 + 5\)
\(P_5 = X^8 + 5 · X^2 + 5 · X^1 + 4\)

Cette correspondance, où pour chaque terme la base d'écriture est remplacée par une indéterminée, met en lumière une suite de polynômes qui décroît au sens lexicographique dans \(\mathbb{N}_8[X]\), un ensemble bien ordonné, donc converge, la seule limite possible respectant ce processus étant le polynôme nul.

La représentation complète d'un nombre n en base b est un peu plus complexe : comme précédemment, n est écrit comme somme de puissances de b, mais la même opération est effectuée avec les exposants, avec les exposants des exposants, et ainsi de suite jusqu'à obtenir une écriture stable.

Ainsi \(266 = 2^8 + 2^3 + 2^1 = 2^{2^{2+1}} + 2^{2+1} + 2^1\).

On peut à présent définir les suites de Goodstein.

Soit n un entier naturel. La n-ième suite de Goodstein est construite de la façon suivante :

\(n_0\) est la représentation complète de \(n\) en base 2
\(n_1\) est obtenu à partir de \(n_0\) en remplaçant tous les 2 par des 3, et en retranchant 1
\(n_2\) est obtenu à partir de \(n_1\) en remplaçant tous les 3 par des 4, et en retranchant 1

Soit, pour n = 266 :
\(n_0 = 2^{2^{2+1}} + 2^{2+1} + 2^1 = 266 \)
\(n_1 = 3^{3^{3+1}} + 3^{3+1} + 3^1 − 1 = 3^{3^{3+1}} + 3^{3+1} + 2 = 443 426 488 243 037 769 948 249 630 619 149 892 886 \approx 10^{38} \)
\(n_2 = 4^{4^{4+1}} + 4^{4+1} + 1 \approx 10^{616}\)
\(n_3 = 5^{5^{5+1}} + 5^{5+1} \approx 10^{10921}\)
\(n_4 = 6^{6^{6+1}} + 6^{6+1} − 1 = 6^{6^{6+1}} + 5 · 6^6 + 5 · 6^5 + 5 · 6^4 + 5 · 6^3 + 5 · 6^2 + 5 · 6^1 + 5 \approx 10^{217 832}\)
\(n_5 = 7^{7^{7+1}} + 7^{7+1} − 1 = 7^{7^{7+1}} + 5 · 7^7 + 5 · 7^5 + 5 · 7^4 + 5 · 7^3 + 5 · 7^2 + 5 · 7^1 + 4 \approx 10^{4 871 822}\)

Théorème (Goodstein) : les suites de Goodstein sont à support fini.

De même que les suites faibles de Goodstein, les suites de Goodstein finissent par s'annuler. Mais le processus est long : la 4-ième suite de Goodstein s'annule après la \(3·2^{402 653 211}-3\)-ème étape (un nombre à plus de 121 millions de chiffres).

L'idée de démonstration est similaire à celle des suites faibles, mais au lieu de polynômes, une correspondance pourra être établie avec une suite d'ordinaux, la base étant substituée par \(\omega\) (le premier ordinal limite).

Pour n = 266 :
\(\beta_0 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + \omega^1 \)
\(\beta_1 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + 2 \)
\(\beta_2 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + 1 \)
\(\beta_3 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} \)
\(\beta_4 = \omega^{\omega^{\omega+1}} + 5 · \omega^\omega + 5 · \omega^5 + 5 · \omega^4 + 5 · \omega^3 + 5 · \omega^2 + 5 · \omega^1 + 5 \)
\(\beta_5 = \omega^{\omega^{\omega+1}} + 5 · \omega^\omega + 5 · \omega^5 + 5 · \omega^4 + 5 · \omega^3 + 5 · \omega^2 + 5 · \omega^1 + 4 \)

Cette suite d'ordinaux est strictement décroissante et donc converge vers le seul élément possible : l'ordinal nul, et il en est de même pour les suites de Goodstein.

À la différence de la convergence des suites faibles de Goodstein, le théorème de Goodstein ne peut être prouvé dans le cadre de l'arithmétique du premier ordre (ou arithmétique de Peano) ; cela a été démontré en 1982 par Kirby et Paris. Toute preuve nécessite de sortir du cadre de l'arithmétique, comme le fait celle basée sur les ordinaux (il apparait ainsi que les ordinaux, grâce à leur bon ordre structurel, peuvent servir à établir la terminaison d'un processus). Le théorème de Goodstein est donc un exemple de proposition de l'arithmétique de Peano vraie mais improuvable en son sein, et constitue une illustration d'énoncé arithmétique indécidable tel que prédit par le premier théorème d'incomplétude de Gödel.

Sources et références (en anglais) :

Reuven L. Goodstein, On the restricted ordinal theorem (1944) - article séminal

Laurie Kirby, Jeff Paris, Accessible Independence Results for Peano Arithmetic (1982) - démonstration de la non-prouvabilité du théorème de Goodstein au sein de l'arithmétique de Peano et introduction du jeu de l'hydre

Bernard G. Hodgson, Herculean or Sisyphean tasks? - article de vulgarisation soulignant que l'annulation des suites de Goodstein est une tâche herculéenne et non sisyphéenne

Michèle Artigue, Ferdinando Arzarello, Susanna Epp, Goodstein Sequences: The Power of a Detour via Infinity - article de vulgarisation

Note

[1] The significant problems we face cannot be solved at the same level of thinking we were at when we created them. Il est difficile de remonter à la source exacte de cette phrase -ou des variantes-, souvent attribuée à Einstein.