ComputabilityComputability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power.
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. La calculabilité (parfois appelée « computationnalité », de l'anglais computability) cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.
Informatique théoriquevignette|Une représentation artistique d'une machine de Turing. Les machines de Turing sont un modèle de calcul. L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique. C'est une branche de la science informatique et la science formelle. Plus généralement, le terme est utilisé pour désigner des domaines ou sous-domaines de recherche centrés sur des vérités universelles (axiomes) en rapport avec l'informatique.
Problème algorithmiqueUn problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier.
Castor affairéUn castor affairé est, en théorie de la calculabilité, une machine de Turing qui maximise son « activité opérationnelle » (comme le nombre de pas effectués ou le nombre de symboles écrits avant son arrêt) parmi toutes les machines de Turing d'une certaine classe. Celles-ci doivent satisfaire certaines spécifications et doivent s'arrêter après être lancées sur un ruban vierge. Une fonction du castor affairé, ou fonction du nombre maximal de pas quantifie cette activité maximale pour une machine de Turing à n états ; ce type de fonction n'est pas calculable.
Complexité de KolmogorovEn informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, , chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff.
HypercalculLe terme hypercalcul désigne les différentes méthodes proposées pour le calcul de fonctions non-Turing-calculables. Il a été initialement introduit par Jack Copeland. On emploie également le terme de calcul super-Turing, bien que celui d'hypercalcul puisse être connoté de la séduisante possibilité qu'une telle machine soit physiquement réalisable. Certains modèles ont été proposés, comme des réseaux de neurones avec des nombres réels en guise de poids, la capacité de conduire une infinité de calculs simultanément ou encore l'aptitude à effectuer des opérations non Turing-calculables, telles que des limites ou des intégrations.
Programmation logiqueLa programmation logique est une forme de programmation qui définit les applications à l'aide : d'une base de faits : ensemble de faits élémentaires concernant le domaine visé par l'application, d'une base de règles : règles de logique associant des conséquences plus ou moins directes à ces faits, d'un moteur d'inférence (ou démonstrateur de théorème ) : exploite ces faits et ces règles en réaction à une question ou requête. Cette approche se révèle beaucoup plus souple que la définition d'une succession d'instructions que l'ordinateur exécuterait.
Algèbre de processusLes algèbres de processus sont une famille de langages formels permettant de modéliser les systèmes (informatiques) concurrents ou distribués. Les algèbres de processus fournissent des outils formels permettant principalement de caractériser les interactions entre processus au sein d'un système concurrent ou distribué, les interactions prenant la forme d'échanges de messages. L'étude des algèbres de processus relève de l'informatique théorique, et leurs applications relèvent principalement du génie logiciel, en particulier des systèmes distribués.
