Dictionnaire > Définitions Personnalités > Gregory John Chaitin
Dictionnaire en ligne
Définitions Sigles Participer Equipe éditoriale Annuaire
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 
Rechercher
 
Tags
Définitions

Gregory John Chaitin

 Thème : PersonnalitésUne définition du thème 'Personnalités'

 Définition

Définition de Gregory John Chaitin  Gregory John Chaitin (1947) logicien, mathématicien américain, créateur de la théorie de l'informatique algorithmique.

 Description

Description de Gregory John Chaitin  Même si la notion d'élégance se trouve sous forme de germe dans l'oeuvre de Leibniz, elle n'est considérée comme formalisée qu'après les travaux de Chaitin. Ce dernier dans la continuation des recherches de Gödel mais aussi de Turing, a su mettre en évidence cette notion afin de la rendre opérationnelle. Pour se faire, il a utilisé la notion des programmes. La définition de Chaitin est la suivante: Un programme élégant est le plus court programme à fournir une sortie donnée. Le théorème de Chaitin peut s'énoncer de la manière suivante: Il n'est en général pas possible de déterminer si un programme donné est élégant ou pas. Il se démontre par l'absurde. En effet, nous considérons qu'il existe un programme E qui puisse tester l'élégance d'un programme donné. Nous construisons alors un programme B qui prend en entrée un entier naturel N et énumère tous les programmes possibles Pk qui sont plus longs que N. B en tant que programme peut faire tourner le programme E sur l'ensemble des programmes Pk qu'il a énumérés jusqu'a ce qu'il trouve un programme qui soit élégant. Alors B fait tourner ce programme et produit la même sortie que ce dernier. Considérons alors le terme suivant: B doit produire un résultat. Il est basé sur le fait qu'il existe une infinité de programmes élégants aussi si le programme E fonctionne comme il a été défini, alors il doit en trouver un, qui possède le résultat escompté. A présent activons le programme B avec l'entier N qui est cette fois égal à la longueur de B+1. B produira alors la même sortie qu'un programme Pk, qui a été déclaré comme élégant par le programme E. Mais Pk est plus long que B aussi Pk ne peut être élégant. Ainsi le programme E n'est pas un testeur d'élégance. Ce qui est absurde. De cette manière, nous voyons que la formalisation de cette notion quelque peu abstraite initialement permet d'obtenir un résultat d'ordre mathématique.

 Auteur

Auteur Nikos Lygeros
Prévisualisation fournie par ThumbshotsOpus of N. Lygeros  Langue du site de destination : Français

 Définitions à consulter

Définitions à consulter Nous vous proposons de consulter également la définition du terme suivant :

  • Kurt Gödel : Kurt Gödel (1906-1978) logicien, mathématicien autrichien.

 Actualité

 Utilisez cette définition !

Consignes pour recopier cette définition sur son site Vous pouvez recopier cette définition sur votre site à condition d'indiquer que la source est le Dico du Net, en utilisant par exemple ce code :

<p>Source <a href="http://www.dicodunet.com/">Dictionnaire en ligne</a> : 
<a href="http://www.dicodunet.com/definitions/personnalites/gregory-john-chaitin.htm">
Gregory John Chaitin</a></p>

 Envoyer à un ami

Envoyez cette définition à un ami Vous pouvez envoyer la définition de Gregory John Chaitin à un ami.

 Sites de l'annuaire

Voici des sites figurant dans notre annuaire (inscription gratuite) :

Offre d'hébergement web professionnel
Hébergement web
 Le Dico du Net
fait confiance à Sivit
pour son hébergement
Testez Sivit à partir de :
1,90 EUR HT/mois
(garantie 30 jours satisfait ou remboursé)
 Publicité

Agent Web Ranking

Agent Web Ranking
Licence   Thumbshots.org