{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Théorème de l'Arrêt (Turing) en Python.\n",
    "##### Adapté de \"The Unknowable\" de Gregory J. Chaitin.\n",
    "(Springer, 1999, ISBN 981-4021-72-5)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Wikipédia:\n",
    "\n",
    "_En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique si le programme s'arrête avec cette entrée ou non._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "_Alan Turing a montré en 1936 que le problème de l'arrêt est indécidable, c'est-à-dire qu'il n'existe pas de programme informatique qui prend comme entrée un programme informatique et et qui, grâce à la seule analyse de ce code, répond VRAI si le programme s'arrête sur son paramètre et FAUX sinon._ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "_En pratique, il n'y a donc pas de méthode générale d'analyse statique capable de déterminer si un programme boucle indéfiniment ou non._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Prélude: Points fixes en Python :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Commençons par une constatation qui peut paraitre surprenante. Definissons la fonction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    return x is f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le moins que l'on puisse dire est que le résultat suivant n'est pas surprenant !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mais on a:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Ainsi, on a un moyen de faire \"travailler\"  un programme (une fonction) sur lui (elle) même."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Le théorème de l'arrêt."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On suppose d'abord qu'on a une fonction \"halts\" qui va répondre True ou False selon que le programme (la fonction) \n",
    "passée en argument s'arrête ou pas. \n",
    "Rappelons que notre but est de montrer qu'une telle fonction (qui prévoit l'arrêt ou non d'un programme) ne peut pas exister.\n",
    "Commençons par supposer que \"halts\" renvoit False :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def halts(prog): \n",
    "    #.....      \n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Définissons une fonction \"Turing\" qui boucle indéfiniment si son argument est un programme qui s'arrête (selon la fonction \"halts\") et qui s'arrête sinon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Turing(prog):\n",
    "    if halts(prog):\n",
    "        print(\"'halts()' says: will halt\")\n",
    "        while True:\n",
    "            pass\n",
    "    else:\n",
    "        print(\"'halts()' says: will loop forever\")\n",
    "        return prog"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "On applique la fonction *Turing* à elle même:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'halts()' says: will loop forever\n",
      "stop !\n"
     ]
    }
   ],
   "source": [
    "Turing(Turing)\n",
    "print(\"stop !\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "et donc Turing(Turing) s'arrête, bien que :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "halts(Turing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "et donc, selon \"halts\", Turing(Turing) **boucle indéfiniment**. Mais, Turing(Turing) **s'arrête**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Changeons la valeur renvoyée par \"halts\" :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def halts(prog):\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### On va vérifier que maintenant Turing(Turing) boucle alors que d'après _halts_ , il devrait s'arrêter ! \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Turing(Turing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Donc, on a fabriqué un programme qui:\n",
    "\n",
    "* ### boucle quand \"halts\" indique qu'il s'arrête,\n",
    "\n",
    "* ### s'arrête sinon.\n",
    "\n",
    "### ce qui est contradictoire avec l'existence d'une fonction \"halts\" qui prédirait l'arrêt on non d'un programme."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Plus sur [Wikipedia](https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_l%27arr%C3%AAt)."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Diaporama",
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}