Logo
Unionpédia
Communication
Disponible sur Google Play
Nouveau! Téléchargez Unionpédia sur votre appareil Android™!
Gratuit
Accès plus rapide que le navigateur!
 

Décidabilité

Indice Décidabilité

En logique mathématique, le terme décidabilité recouvre deux concepts liés: la décidabilité logique et la décidabilité ''algorithmique''.

66 relations: Académie royale des sciences, des lettres et des beaux-arts de Belgique, Alan Turing, Alfred Tarski, Algorithme, Algorithmique, Alonzo Church, Analyse non standard, Arithmétique de Presburger, Axiome des parallèles, Axiomes de Peano, Éléments (Euclide), Élisabeth Bouscaren, Énigme de combustion de mèches, Caractéristique d'un anneau, Chen Chung Chang, Codage de Gödel, Complétude, Corps algébriquement clos, Corps réel clos, Correction (logique), Décision, Dixième problème de Hilbert, Ensemble récursif, Entier naturel, Euclide, Eugenio Beltrami, Géométrie euclidienne, Géométrie non euclidienne, Hiérarchie arithmétique, Hypothèse du continu, Informatique, Kurt Gödel, Lambda-calcul, Liste d'énoncés indécidables dans ZFC, Livre I des Éléments d'Euclide, Logique classique, Logique combinatoire, Logique mathématique, Machine de Turing, Mathématiques, Nombre cardinal, Nombre premier, Nombre réel, Oméga de Chaitin, Paul Cohen, Pierre Wolper, Problème de correspondance de Post, Problème de décision, Problème de l'arrêt, Problème de la décision, ..., Récursivement énumérable, Stephen Cole Kleene, Thèse de Church, Théorème de complétude de Gödel, Théorème de Goodstein, Théorème de Kruskal, Théorème de Rice, Théorème de Tarski, Théorèmes d'incomplétude de Gödel, Théorie axiomatique, Théorie de la calculabilité, Théorie de la complexité (informatique théorique), Théorie des ensembles de Zermelo-Fraenkel, Théorie des modèles, Théorie k-catégorique, Turing-complet. Développer l'indice (16 plus) »

Académie royale des sciences, des lettres et des beaux-arts de Belgique

L'Académie royale des sciences, des lettres et des beaux-arts de Belgique, créée en 1772, souvent abrégée en Académie royale de Belgique et surnommée « la Thérésienne », est l'académie scientifique et artistique de la Communauté française de Belgique.

Nouveau!!: Décidabilité et Académie royale des sciences, des lettres et des beaux-arts de Belgique · Voir plus »

Alan Turing

Alan Turing vers 1938. Alan Mathison Turing, né le à Londres et mort le à Wilmslow, est un mathématicien et cryptologue britannique, auteur de travaux qui fondent scientifiquement l'informatique.

Nouveau!!: Décidabilité et Alan Turing · Voir plus »

Alfred Tarski

Alfred Tarski, né Alfred Teitelbaum le à Varsovie et mort le à Berkeley en Californie, est un logicien et un philosophe polonais, un des maîtres de l'école polonaise de logique et l'un des mathématiciens logiciens les plus éminents du, fondateur de la théorie des modèles et de la sémantique formelle.

Nouveau!!: Décidabilité et Alfred Tarski · Voir plus »

Algorithme

triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes.

Nouveau!!: Décidabilité et Algorithme · Voir plus »

Algorithmique

Organigramme de programmation représentant l'algorithme d'Euclide. Lalgorithmique est l'étude et la production de règles et techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est-à-dire de processus systématiques de résolution d'un problème permettant de décrire précisément des étapes pour résoudre un problème algorithmique.

Nouveau!!: Décidabilité et Algorithmique · Voir plus »

Alonzo Church

Alonzo Church (Washington - Hudson) est un mathématicien (logicien) américain à qui l'on doit certains des fondements de l'informatique théorique.

Nouveau!!: Décidabilité et Alonzo Church · Voir plus »

Analyse non standard

En mathématiques, et plus précisément en analyse, l'analyse non standard est un ensemble d'outils développés depuis 1960 afin de traiter la notion d'infiniment petit de manière rigoureuse.

Nouveau!!: Décidabilité et Analyse non standard · Voir plus »

Arithmétique de Presburger

En logique mathématique, l'arithmétique de Presburger est la théorie du premier ordre des nombres entiers naturels munis de l'addition.

Nouveau!!: Décidabilité et Arithmétique de Presburger · Voir plus »

Axiome des parallèles

L’axiome d'Euclide, dit également cinquième postulat d’Euclide, est dû au savant grec Euclide.

Nouveau!!: Décidabilité et Axiome des parallèles · Voir plus »

Axiomes de Peano

Giuseppe Peano En mathématiques, les axiomes de Peano sont des axiomes pour l'arithmétique proposés initialement à la fin du par Giuseppe Peano, et qui connaissent aujourd'hui plusieurs présentations qui ne sont pas équivalentes, suivant la théorie sous-jacente, théorie des ensembles, logique du second ordre ou d'ordre supérieur, ou logique du premier ordre.

Nouveau!!: Décidabilité et Axiomes de Peano · Voir plus »

Éléments (Euclide)

texte.

Nouveau!!: Décidabilité et Éléments (Euclide) · Voir plus »

Élisabeth Bouscaren

Élisabeth Bouscaren (née le) est une mathématicienne française qui travaille dans les domaines de la géométrie algébrique, l'algèbre et la logique mathématique (théorie des modèles).

Nouveau!!: Décidabilité et Élisabeth Bouscaren · Voir plus »

Énigme de combustion de mèches

En mathématiques récréatives, les énigmes de combustion de mèches sont un type de casse-tête mathématique dans lesquels sont données des longueurs de cordes ou de mèches brûlant (de manière non uniforme) pendant un temps donné pris pour unité, et qu'on doit allumer de manière à mesurer une certaine durée.

Nouveau!!: Décidabilité et Énigme de combustion de mèches · Voir plus »

Caractéristique d'un anneau

En algèbre, la caractéristique d'un anneau (unitaire) A est par définition l'ordre pour la loi additive de l'élément neutre de la loi multiplicative si cet ordre est fini; si cet ordre est infini, la caractéristique de l'anneau est par définition zéro.

Nouveau!!: Décidabilité et Caractéristique d'un anneau · Voir plus »

Chen Chung Chang

Chen Chung Chang est un mathématicien américain spécialisé en théorie des modèles.

Nouveau!!: Décidabilité et Chen Chung Chang · Voir plus »

Codage de Gödel

En logique mathématique, un codage de Gödel (ou numérotation de Gödel) est une fonction qui attribue à chaque symbole et formule bien-formée de certains langages formels un entier naturel unique, appelé son code de Gödel, ou numéro de Gödel.

Nouveau!!: Décidabilité et Codage de Gödel · Voir plus »

Complétude

La notion de complétude est utilisée dans plusieurs domaines scientifiques.

Nouveau!!: Décidabilité et Complétude · Voir plus »

Corps algébriquement clos

En mathématiques, un corps commutatif K est dit algébriquement clos si tout polynôme de degré supérieur ou égal à un, à coefficients dans K, admet (au moins) une racine dans K. Autrement dit, c'est un corps qui n'a pas d'extension algébrique propre.

Nouveau!!: Décidabilité et Corps algébriquement clos · Voir plus »

Corps réel clos

En mathématiques, un corps réel clos est un corps totalement ordonnable dont aucune extension algébrique propre n'est totalement ordonnable.

Nouveau!!: Décidabilité et Corps réel clos · Voir plus »

Correction (logique)

En logique, la forme d'une argumentation déductive est correcte si et seulement si elle est valide et que toutes ses prémisses sont effectivement vraies.

Nouveau!!: Décidabilité et Correction (logique) · Voir plus »

Décision

La décision est le fait d'un acteur (ou d'un ensemble plus ou moins cohérent d'acteurs) qui effectue un choix entre plusieurs solutions susceptibles de résoudre le problème, ou la situation, auquel il est confronté.

Nouveau!!: Décidabilité et Décision · Voir plus »

Dixième problème de Hilbert

Le dixième problème de Hilbert fait partie de la liste des 23 problèmes posés par David Hilbert en 1900 à Paris, lors de sa conférence au congrès international des mathématiciens.

Nouveau!!: Décidabilité et Dixième problème de Hilbert · Voir plus »

Ensemble récursif

En théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens de la logique mathématique.

Nouveau!!: Décidabilité et Ensemble récursif · Voir plus »

Entier naturel

En mathématiques, un entier naturel est un nombre permettant fondamentalement de compter des objets considérés comme des unités équivalentes: un jeton, deux jetons… une carte, deux cartes, trois cartes… Un tel nombre entier peut s'écrire avec une suite finie de chiffres en notation décimale positionnelle (sans signe et sans virgule).

Nouveau!!: Décidabilité et Entier naturel · Voir plus »

Euclide

Euclide (en Eukleídês), dit parfois Euclide d'Alexandrie, est un mathématicien de la Grèce antique, auteur d’un traité de mathématiques, qui constitue l'un des textes fondateurs de cette discipline en Occident.

Nouveau!!: Décidabilité et Euclide · Voir plus »

Eugenio Beltrami

Eugenio Beltrami (1835-1900), appelé Eugène Beltrami en français, est un mathématicien et physicien italien.

Nouveau!!: Décidabilité et Eugenio Beltrami · Voir plus »

Géométrie euclidienne

La géométrie euclidienne commence avec les Éléments d'Euclide, qui est à la fois une somme des connaissances géométriques de l'époque et une tentative de formalisation mathématique de ces connaissances.

Nouveau!!: Décidabilité et Géométrie euclidienne · Voir plus »

Géométrie non euclidienne

La géométrie non euclidienne (GNE) est, en mathématiques, une théorie géométrique ayant recours aux axiomes et postulats posés par Euclide dans les Éléments, sauf le postulat des parallèles.

Nouveau!!: Décidabilité et Géométrie non euclidienne · Voir plus »

Hiérarchie arithmétique

Theory of Computation'', Springer 2006.. En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Stephen Cole Kleene, est une hiérarchie des sous-ensembles de l'ensemble N des entiers naturels définissables dans le langage du premier ordre de l'arithmétique de Peano.

Nouveau!!: Décidabilité et Hiérarchie arithmétique · Voir plus »

Hypothèse du continu

En théorie des ensembles, l'hypothèse du continu (HC), due à Georg Cantor, affirme qu'il n'existe aucun ensemble dont le cardinal est strictement compris entre le cardinal de l'ensemble des entiers naturels et celui de l'ensemble des nombres réels.

Nouveau!!: Décidabilité et Hypothèse du continu · Voir plus »

Informatique

bibliothèque d'Art et d'Archéologie de Genève (2017). L'informatique est un domaine d'activité scientifique, technique, et industriel concernant le traitement automatique de l'information numérique par l'exécution de programmes informatiques hébergés par des dispositifs électriques-électroniques: des systèmes embarqués, des ordinateurs, des robots, des automates Ces champs d'application peuvent être séparés en deux branches.

Nouveau!!: Décidabilité et Informatique · Voir plus »

Kurt Gödel

Kurt Gödel, né le à Brünn et mort le à Princeton (New Jersey), est un logicien et mathématicien autrichien naturalisé américain.

Nouveau!!: Décidabilité et Kurt Gödel · Voir plus »

Lambda-calcul

Le lambda-calcul (ou λ-calcul) est un système formel inventé par Alonzo Church dans les années 1930, qui fonde les concepts de fonction et d'application.

Nouveau!!: Décidabilité et Lambda-calcul · Voir plus »

Liste d'énoncés indécidables dans ZFC

Cette liste d'énoncés indécidables dans ZFC est formée d'affirmations dont il est démontré qu'elles sont indépendantes de la théorie des ensembles ZFC (la théorie prise comme fondement des mathématiques contemporaines, formée des axiomes de Zermelo–Fraenkel auxquels on adjoint l'axiome du choix), c'est-à-dire que cette théorie (en supposant qu'elle soit consistante) ne peut ni les démontrer, ni démontrer leur négation.

Nouveau!!: Décidabilité et Liste d'énoncés indécidables dans ZFC · Voir plus »

Livre I des Éléments d'Euclide

Le livre I des Éléments d'Euclide pose les fondements pour la suite de l'ouvrage.

Nouveau!!: Décidabilité et Livre I des Éléments d'Euclide · Voir plus »

Logique classique

La logique classique est la première formalisation du langage et du raisonnement mathématique développée à partir de la fin du en logique mathématique.

Nouveau!!: Décidabilité et Logique classique · Voir plus »

Logique combinatoire

En logique mathématique, la logique combinatoire est une théorie logique introduite par Moses Schönfinkel en 1920 lors d'une conférence et développée dès 1929 par Haskell Brooks Curry pour supprimer le besoin de variables en mathématiques, pour formaliser rigoureusement la notion de fonction et pour minimiser le nombre d'opérateurs nécessaires pour définir le calcul des prédicats à la suite de Henry M. Sheffer.

Nouveau!!: Décidabilité et Logique combinatoire · Voir plus »

Logique mathématique

La logique mathématique ou métamathématique est une discipline des mathématiques introduite à la fin du, qui s'est donné comme objet l'étude des mathématiques en tant que langage.

Nouveau!!: Décidabilité et Logique mathématique · Voir plus »

Machine de Turing

En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur.

Nouveau!!: Décidabilité et Machine de Turing · Voir plus »

Mathématiques

Les mathématiques (ou la mathématique) sont un ensemble de connaissances abstraites résultant de raisonnements logiques appliqués à des objets divers tels que les ensembles mathématiques, les nombres, les formes, les structures, les transformations; ainsi qu'aux relations et opérations mathématiques qui existent entre ces objets.

Nouveau!!: Décidabilité et Mathématiques · Voir plus »

Nombre cardinal

Le nombre cardinal des deux ensembles X et Y est 4 En linguistique, les nombres entiers naturels zéro, un, deux, trois, etc.

Nouveau!!: Décidabilité et Nombre cardinal · Voir plus »

Nombre premier

Entiers naturels de zéro à cent. Les nombres premiers sont marqués en rouge. 7 est premier car il admet exactement deux diviseurs positifs distincts. Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs.

Nouveau!!: Décidabilité et Nombre premier · Voir plus »

Nombre réel

En mathématiques, un nombre réel est un nombre qui peut être représenté par une partie entièreCette partie entière par troncature, désignant les chiffres « à gauche de la virgule » ne correspond pas forcément à la partie entière par défaut: dans le cas d’un nombre réel négatif comme, la partie entière par défaut vaut.

Nouveau!!: Décidabilité et Nombre réel · Voir plus »

Oméga de Chaitin

Un nombre Oméga de Chaitin est une suite de bits représentant, sous forme concentrée, la solution du problème de l'arrêt pour tous les programmes d'une machine de Turing universelle donnée. En théorie algorithmique de l'information, une constante Oméga de Chaitin (nombres définis et étudiés par Gregory Chaitin) caractérise de manière univoque et mathématiquement précise un nombre réel, qui possède la particularité d'être aléatoire et de ne pas être calculable au sens de Turing: un algorithme donné ne permet de calculer qu'un nombre fini de ses décimales.

Nouveau!!: Décidabilité et Oméga de Chaitin · Voir plus »

Paul Cohen

Paul Joseph Cohen (1934 - 2007) est un mathématicien américain.

Nouveau!!: Décidabilité et Paul Cohen · Voir plus »

Pierre Wolper

Pierre Wolper, né le à Liège, est un informaticien belge.

Nouveau!!: Décidabilité et Pierre Wolper · Voir plus »

Problème de correspondance de Post

En mathématiques et en informatique théorique, et plus précisément en théorie de la calculabilité, le problème de correspondance de Post (PCP) est un problème de décision indécidable qui fut introduit par Emil Post en 1946.

Nouveau!!: Décidabilité et Problème de correspondance de Post · Voir plus »

Problème de décision

En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ».

Nouveau!!: Décidabilité et Problème de décision · Voir plus »

Problème de l'arrêt

L'animation illustre une machine impossible: il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.

Nouveau!!: Décidabilité et Problème de l'arrêt · Voir plus »

Problème de la décision

En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples: système à la Hilbert, calcul des séquents, déduction naturelle).

Nouveau!!: Décidabilité et Problème de la décision · Voir plus »

Récursivement énumérable

En théorie de la calculabilité, un ensemble d'entiers naturels est récursivement énumérable ou semi-décidable si.

Nouveau!!: Décidabilité et Récursivement énumérable · Voir plus »

Stephen Cole Kleene

Stephen Cole Kleene, né le à Hartford (Connecticut) et mort le à Madison (Wisconsin), est un mathématicien et logicien américain.

Nouveau!!: Décidabilité et Stephen Cole Kleene · Voir plus »

Thèse de Church

La thèse de Church est une thèse concernant la définition de la notion de calculabilité.

Nouveau!!: Décidabilité et Thèse de Church · Voir plus »

Théorème de complétude de Gödel

En logique mathématique, le théorème de complétude du calcul des prédicats du premier ordre dresse une correspondance entre la sémantique et les démonstrations d'un système de déduction en logique du premier ordre.

Nouveau!!: Décidabilité et Théorème de complétude de Gödel · Voir plus »

Théorème de Goodstein

En mathématiques, et plus précisément en logique mathématique, le théorème de Goodstein est un énoncé arithmétique portant sur des suites, dites suites de Goodstein.

Nouveau!!: Décidabilité et Théorème de Goodstein · Voir plus »

Théorème de Kruskal

En mathématiques, le théorème des arbres de Kruskal est un résultat de théorie des graphes conjecturé en 1937 par Andrew Vázsonyi et démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski, affirmant que l'ensemble des arbres étiquetés par un ensemble muni d'un bel ordre est lui-même muni d'un bel ordre.

Nouveau!!: Décidabilité et Théorème de Kruskal · Voir plus »

Théorème de Rice

En informatique théorique, plus précisément en théorie de la calculabilité, le théorème de Rice énonce que toute propriété sémantique non triviale d'un programme est indécidable.

Nouveau!!: Décidabilité et Théorème de Rice · Voir plus »

Théorème de Tarski

En logique mathématique, le théorème de Tarski, ou théorème de non définissabilité de Tarski, s'énonce informellement ainsi:On ne peut définir dans le langage de l'arithmétique la vérité des énoncés de ce langage.

Nouveau!!: Décidabilité et Théorème de Tarski · Voir plus »

Théorèmes d'incomplétude de Gödel

Les théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, publiés par Kurt Gödel en 1931 dans son article (« Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés »).

Nouveau!!: Décidabilité et Théorèmes d'incomplétude de Gödel · Voir plus »

Théorie axiomatique

Quand on parle de théorie mathématique, on fait référence à une somme d'énoncés, de définitions, de méthodes de preuve, etc.

Nouveau!!: Décidabilité et Théorie axiomatique · Voir plus »

Théorie de la calculabilité

La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique.

Nouveau!!: Décidabilité et Théorie de la calculabilité · Voir plus »

Théorie de la complexité (informatique théorique)

P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.

Nouveau!!: Décidabilité et Théorie de la complexité (informatique théorique) · Voir plus »

Théorie des ensembles de Zermelo-Fraenkel

L'appartenance En mathématiques, la théorie des ensembles de Zermelo-Fraenkel, abrégée en ZF, est une axiomatisation en logique du premier ordre de la théorie des ensembles telle qu'elle avait été développée dans le dernier quart du par Georg Cantor.

Nouveau!!: Décidabilité et Théorie des ensembles de Zermelo-Fraenkel · Voir plus »

Théorie des modèles

La théorie des modèles est une branche de la logique mathématique qui traite de la construction et de la classification des structures.

Nouveau!!: Décidabilité et Théorie des modèles · Voir plus »

Théorie k-catégorique

En logique mathématique, une théorie est dite k-catégorique pour un nombre cardinal k si elle a exactement un modèle de cardinalité k (à isomorphisme près).

Nouveau!!: Décidabilité et Théorie k-catégorique · Voir plus »

Turing-complet

En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-complete) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing.

Nouveau!!: Décidabilité et Turing-complet · Voir plus »

Redirections ici:

Décidabilité et indécidabilité, Décidable, Indécidabilité, Indécidable, Proposition indécidable.

SortantEntrants
Hey! Nous sommes sur Facebook maintenant! »