Décidable

"décidable" dans l'encyclopédie

• MÉTALOGIQUE

  • Écrit par Françoise ARMENGAUD
  • 2 318 mots

  La logique des propositions est saturée du point de vue syntaxique et sémantique ; elle est décidable et non contradictoire. La logique des prédicats du premier ordre est non contradictoire, décidable pour les prédicats absolus et certaines classes d'expressions de la logique des relations. En ce qui concerne la logique des prédicats d'ordre supérieur, les tentatives pour montrer leur caractère non contradictoire (ou celui d'un système assez puissant pour formaliser les mathématiques) ont échoué.

• CHURCH ALONZO (1903-1995)

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

  En cela, l'arithmétique diffère du calcul propositionnel, décidable par tables de vérité, mais non du calcul des prédicats dans son ensemble. C'est tout le projet qu'avait formé Hilbert d'introduire des démonstrations effectives en mathématiques qui devient irréalisable. Tel est en substance le « théorème de Church » (1936), qu'on ne doit pas confondre avec la « thèse de Church », encore que les deux soient liés.

• CATALAN ÉQUATION DE

  • Écrit par Maurice MIGNOTTE
  • 2 804 mots

  Pour un logicien, le problème de Catalan est donc décidable, mais l'ensemble fini obtenu par cette méthode est bien trop grand pour une recherche exhaustive par ordinateur. Combinée avec certains résultats algébriques, cette méthode a cependant permis aux Français Maurice Mignotte et Yves Roy (Strasbourg) de démontrer en 1996 que p et q devaient être supérieurs à 100 000.

• TURING ALAN MATHISON (1912-1954)

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

  En 1936, Turing et Church montrent, chacun de son côté, que ce problème n'a en général pas de solution, prouvant qu'aucun système arithmétique formel cohérent n'est décidable. Ce résultat et bien d'autres, notamment les théorèmes d'incomplétude du mathématicien et logicien Kurt Gödel, mettent fin au rêve d'un système qui pourrait bannir à jamais l'ignorance des mathématiques.

• RÉCURSIVITÉ, logique mathématique

  • Écrit par Kenneth Mc ALOON, Bernard JAULIN et Jean-Pierre RESSAYRE
  • 49 033 mots

  Un ensemble X ⊂ Np est dit récursif (on dit aussi décidable) si sa fonction caractéristique est récursive. Intuitivement, cela signifie qu'il existe un algorithme permettant de décider si un élément quelconque de Np appartient ou non à X. Ainsi, les ensembles finis, l'ensemble des nombres premiers, l'ensemble des nombres qui sont somme de deux nombres premiers impairs.