CALCULABILITÉ

Articles

• CALCUL, mathématique

  • Écrit par Philippe FLAJOLET
  • 1 785 mots
  Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par...

• COMPLEXITÉ, mathématique

  • Écrit par Jean-Paul DELAHAYE
  • 1 626 mots

  Au cœur de l'informatique théorique, la théorie du calcul – ou théorie de la calculabilité – née dans la décennie 1930 des travaux de Kurt Gödel (1906-1978), Alan Turing (1912-1954) et Alonzo Church (1903-1995), répond à des questions sur ce qui est faisable dans l'absolu par le...

• GÖDEL KURT (1906-1978)

  • Écrit par Daniel ANDLER
  • 2 292 mots
  Les résultats d'incomplétude conduisaient également à la définition générale de fonction récursive, par Herbrand et Gödel, et à l'élucidation par Turing de la notion de calculabilité, qui permettait de dégager la véritable généralité des théorèmes de Gödel.

• HILBERT DAVID (1862-1943)

  • Écrit par Rüdiger INHETVEEN, Jean-Michel KANTOR, Christian THIEL
  • 14 726 mots
  • 1 média
  D'autre part, un ensemble d'entiersest dit calculable s'il existe un algorithme permettant de déterminer en un nombre fini d'étapes si un nombre lui appartient ou non. D'après la théorie des algorithmes, on connaît l'existence d'un ensemble récursivement énumérable qui ne soit pas calculable. Les deux...

• TURING MACHINE DE

  • Écrit par Bernard PIRE
  • 197 mots

  Dans l'article « On computable numbers, with an application to the Entscheidungsproblem », publié en 1936 dans les Proceedings of the Mathematical Society, Alan Mathison Turing (1912-1954) montre qu'il existe des nombres définissables qui ne sont pas calculables. Cela implique qu'il n'existe...

• PENSÉE

  • Écrit par Pascal ENGEL
  • 8 304 mots
  • 1 média
  ...la forme d'inscriptions de symboles, après le passage de la machine par divers états. Une machine de Turing est la réalisation de la notion logique de calculabilité : si une fonction est calculable, elle l'est par une telle machine. Or, selon la « thèse de Church », il n'y a pas d'algorithme pour la calculabilité...

• RÉCURSIVITÉ, logique mathématique

  • Écrit par Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE
  • 8 914 mots
  Définition. Une fonction f ∈ *F^(p) est dite calculable par programme, et on note f ∈ *F_P^(p) s'il existe un programme écrit à l'aide des quatre instructions ci-dessus et de l'instruction « arrêt » tel que, si x₁, x₂, ..., x_p sont les nombres placés avant le début...

• TURING ALAN MATHISON (1912-1954)

  • Écrit par B. Jack COPELAND
  • 1 561 mots
  • 1 média
  ...mathématiques. (En fait, Turing et Church montrent même que certains systèmes purement logiques, bien moins solides que l'arithmétique, sont indécidables.) Un important argument de Turing et Church est que la classe des fonctions lambda-définissables (fonctions des entiers naturels dont la valeur peut être...