Turing meets Python and Julia

Théorème de l'Arrêt (Turing Halting Theorem, 1936) en Python et en Julia.

(Apologize for using French; translation is easy, but I am lazzy).

Adapté de The Unknowable de Gregory J. Chaitin.

(Springer, 1999, ISBN 981-4021-72-5).

Dans le livre cité ci-dessus G. Chaitin propose une démonstration en Lisp du théorème de l'Arrêt (ainsi que des démonstrations du théorème de Godel et de son théorème sur les programmes élégants, également en Lisp).

Il m'a paru plus accessible de donner des présentations en Python et en Julia, ces deux langages étant bien adaptés. Et puis c'est un exercice amusant !

Comment exécuter ces programmes ?

Dans les deux cas, il s'agit de notebooks jupyter, ce qui permet d'obtenir une version discursive des programmes.

Installations préalables :

• Vous devez d'abord installer jupyter, qui va nécessiter une installation basique de python 3.
  Le plus simple est d'utiliser pip ou conda selon vos préférences. Voir le lien.

• Pour le notebook Julia, vous devez d'abord installer... Julia. Le mieux est d'installer une version stable récente depuis le site Julia. Il faut ensuite installer [IJulia]( (c'est un package julia) depuis julia.

Exécution des notebooks:

Il suffit de lancer jupyter en ligne de commande dans le répertoire où vous avez cloné ce repository:

>jupyter notebook

et voilà, la suite est évidente.

• N'oubliez pas de décommenter la ligne Turing() --celle qui boucle ! c'est commenté pour faire plaisir à github.--