Complexité algorithmique et théorie algorithmique de l’information

    <p class=default>
      
        Une fonction portant sur une suite de chiffres binaires est dite calculable s’il existe 
        une machine de Turing qui, partant de la même suite, donne le même résultat.
      
      
        <u>fn 1 <ch9bft.htm></u>
      
      
         La thèse de Church-Turing stipule que toute fonction calculable dans un sens intuitif 
        (par un homme par exemple) l’est dans le sens formel ici exposé. La machine universelle de 
        Turing est alors une machine sur laquelle on peut exécuter toutes les tâches qu’on 
        accomplirait avec des machines de Turing particulières.
      
      
        <u>fn 2 <ch9bft.htm></u>
      
      
         
      
      
        
      
    <br/>

      
        
      
    </p>