CALCULABILITÉ

CALCUL, mathématique

  • Écrit par 
  • Philippe FLAJOLET
  •  • 1 782 mots

Dans le chapitre « 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'agi […] Lire la suite☛ http://www.universalis.fr/encyclopedie/calcul-mathematique/#i_82679

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 627 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 calcul avec un ordinateur. Elle énonce des résultats négatifs du type : il est impossible d'écrire un programme – aussi […] Lire la suite☛ http://www.universalis.fr/encyclopedie/complexite-mathematique/#i_82679

GÖDEL KURT (1906-1978)

  • Écrit par 
  • Daniel ANDLER
  •  • 2 293 mots

Dans le chapitre « L'œuvre »  : […] Les travaux de Gödel ont été exposés et situés dans leur contexte mathématique et épistémologique (cf. logique mathématique , hilbert , fondements des mathématiques et problèmes de hilbert ). Aussi nous contenterons-nous ici d'un bref aperçu. Le premier grand résultat est celui de la complétude du calcul des prédicats. Dans leur Grundzüge der Theoretischen Logik , paru en 1928, Hilbert et Ackerm […] Lire la suite☛ http://www.universalis.fr/encyclopedie/kurt-godel/#i_82679

HILBERT DAVID (1862-1943)

  • Écrit par 
  • Rüdiger INHETVEEN, 
  • Jean-Michel KANTOR, 
  • Christian THIEL
  •  • 14 855 mots
  •  • 1 média

Dans le chapitre « Problème 10 : résolubilité des équations diophantiennes »  : […] Il faut bien sûr saluer le coup de tonnerre que fut la résolution du problème de Fermat par Wiles (1994). Hilbert ne proposait que de chercher un algorithme (nous emploierons ce terme, qui n'est pas celui qu'emploie Hilbert, en admettant son sens intuitif) permettant de déterminer en un nombre fini d'opérations si une équation diophantienne a des solutions (entières). La théorie des fonctions réc […] Lire la suite☛ http://www.universalis.fr/encyclopedie/david-hilbert/#i_82679

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 pas de solution au célèbre problème de la décision formulé par David Hilbert. Pour cette démonstration, le […] Lire la suite☛ http://www.universalis.fr/encyclopedie/machine-de-turing/#i_82679

PENSÉE

  • Écrit par 
  • Pascal ENGEL
  •  • 8 282 mots
  •  • 1 média

Dans le chapitre « Pensée, machines et fonctionnalisme »  : […] Tout cela peut-il être tenu comme une réfutation définitive du cartésianisme ? Jusqu'à un certain point seulement. Ce dernier s'accorde avec la psychologie du sens commun quand il traite les états mentaux comme des causes du comportement. Mais la difficulté propre au dualisme a toujours été d'expliquer l'interaction entre le mental et le physique, qu'il rend mystérieuse. Supprime-t-on le problème […] Lire la suite☛ http://www.universalis.fr/encyclopedie/pensee/#i_82679

RÉCURSIVITÉ, logique mathématique

  • Écrit par 
  • Kenneth Mc ALOON, 
  • Bernard JAULIN, 
  • Jean-Pierre RESSAYRE
  •  • 9 371 mots

Dans le chapitre « Définition informatique »  : […] Nous donnerons cette définition de façon informelle, bien qu'elle puisse être présentée de façon rigoureuse dans le cadre de la théorie des automates. On dispose de « boîtes » (ou registres de mémoire) dans lesquelles on peut enregistrer des nombres entiers naturels. Si n est le numéro d'une boîte, on désigne par […] Lire la suite☛ http://www.universalis.fr/encyclopedie/recursivite-logique-mathematique/#i_82679

TURING ALAN MATHISON (1912-1954)

  • Écrit par 
  • B. Jack COPELAND
  •  • 1 552 mots
  •  • 1 média

Dans le chapitre « Jeunesse et études universitaires  »  : […] Alan Mathison Turing naît le 23 juin 1912 à Londres. Fils d'un fonctionnaire britannique de l'administration indienne, Turing commence à étudier les mathématiques au King's College de l'université de Cambridge en 1931. Après avoir obtenu son diplôme en 1934, il obtient une bourse d'enseignant chercheur au King's College en reconnaissance de ses travaux sur la théorie des probabilités. En 1936, l […] Lire la suite☛ http://www.universalis.fr/encyclopedie/alan-mathison-turing/#i_82679