Model of computationIn computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.
Machine à registres illimitésEn informatique, une machine à registres illimités ou URM (de l'anglais : Unlimited Register Machine) est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tout comme les machines de Turing et le lambda-calcul. Une URM est Turing-complète. Les registres de la machine sont représentés par : et peuvent contenir des éléments de . Un programme pour cette machine est représenté par toute suite de la forme : qui contient une suite finie d'instructions.
Machine à compteursUne machine à compteurs est un modèle de calcul très rudimentaire. Les machines à compteurs sont parfois appelées machines à registres ou machines de Minsky. Dans sa version la plus simple une machine à compteurs est composée de deux compteurs (ou registres) et d'un programme. Chaque compteur est un entier naturel (non borné).
Pointer machineIn theoretical computer science, a pointer machine is an atomistic abstract computational machine model akin to the random-access machine. A pointer algorithm could also be an algorithm restricted to the pointer machine model. Depending on the type, a pointer machine may be called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc. (cf Ben-Amram 1995). At least three major varieties exist in the literature—the Kolmogorov-Uspenskii model (KUM, KU-machine), the Knuth linking automaton, and the Schönhage Storage Modification Machine model (SMM).
Random-access stored-program machineIn theoretical computer science the random-access stored-program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory. The RASP is a random-access machine (RAM) model that, unlike the RAM, has its program in its "registers" together with its input. The registers are unbounded (infinite in capacity); whether the number of registers is finite is model-specific. Thus the RASP is to the RAM as the Universal Turing machine is to the Turing machine.
OrdinateurUn ordinateur est un système de traitement de l'information programmable tel que défini par Alan Turing et qui fonctionne par la lecture séquentielle d'un ensemble d'instructions, organisées en programmes, qui lui font exécuter des opérations logiques et arithmétiques. Sa structure physique actuelle fait que toutes les opérations reposent sur la logique binaire et sur des nombres formés à partir de chiffres binaires.
Machine de TuringEn informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.
Machine abstraiteEn informatique théorique, et notamment en théorie des automates, un automate abstrait ou une machine abstraite est un modèle théorique d'un ordinateur digital et discret. Il importe peu, dans ce cadre, de savoir si cet appareil peut effectivement être construit, mais plutôt d'appréhender, par ce modèle simplifié, le fonctionnement des machines, et de les comparer entre eux. La notion d'automate ou de machine abstraite, aussi appelé « modèle de machine » joue un rôle central en informatique théorique.
Machine de Turing universellevignette|upright=1.5|Une machine de Turing quelconque M réalise un calcul à partir d'une entrée écrite sur son ruban. Une machine de Turing universelle U simule le calcul de M sur l'entrée de M à partir d'une description de M et de l'entrée de M écrits sur le ruban de U. En informatique, plus précisément en informatique théorique, une machine de Turing universelle est une machine de Turing qui peut simuler n'importe quelle machine de Turing sur n'importe quelle entrée.
Fonction récursiveEn informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives).
