Calculabilité

"calculabilité" dans l'encyclopédie

• CHURCH ALONZO (1903-1995)

  • Écrit par Françoise ARMENGAUD
  • 3 381 mots

  Le statut intuitif de la calculabilité effective exclut toute justification complète de la thèse, mais l'identification que celle-ci opère est très plausible. Néanmoins, la thèse de Church fut discutée. Elliot Mendelsohn a résumé et critiqué les principales objections dans son article « On Some Recent Criticism of Church's Thesis », in Notre Dame Journal of Formal Logic, vol.

• CALCUL, mathématique

  • Écrit par Philippe FLAJOLET
  • 9 818 mots

  Calculabilité et algorithmique 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 calcul, parmi l'infini des assertions mathématiques possibles, celles qui sont vraies : il s'agit là de l'un des célèbres théorèmes de Kurt Gödel.

• PREMIERS ORDINATEURS (repères chronologiques)

  • Écrit par Pierre MOUNIER-KUHN
  • 6 100 mots

  Dans cet article sur la calculabilité et le problème de la décision, il imagine une « machine » conceptuelle destinée à prouver les limites de la calculabilité. Pendant la Seconde Guerre mondiale, Turing concevra des machines cryptographiques. Il participera ensuite à l'invention de l'ordinateur et au développement de la science informatique en Grande-Bretagne, en jetant les bases de l'intelligence artificielle.

• POST EMIL LEON (1897-1954)

  • Écrit par Bernard JAULIN
  • 3 419 mots

  Quine écrivait en 1954 à l'occasion de la mort de Post : « Le concept de fonction récursive, concept mathématique précis rendant compte de la notion de calculabilité, fut découvert indépendamment et sous des formes différentes par quatre mathématiciens et Post fut l'un d'entre eux », et, en 1972, W. Quine ajoutait : « La théorie des fonctions récursives dont Post fut un des cofondateurs est deux fois plus âgée qu'en 1954 ; elle a bien montré, depuis, quel champ fertile elle est.

• INFORMATIQUE Vue d'ensemble

  • Écrit par Jean-Paul DELAHAYE
  • 6 401 mots

  La théorie de la calculabilité, née de la logique mathématique, s'est considérablement développée et précisée, donnant naissance à la théorie des classes de complexité (P, NP, EXP, etc.) et à la théorie algorithmique de l'information – ou théorie de la complexité de Kolmogorov –, qui est venue compléter la théorie de l'information de Shannon. La théorie des langages et des automates se place au cœur des techniques de programmation et de compilation.