Complexité et décidabilité |
Contents
INTRODUCTION | 3 |
SIMULATION DALGORITHMES | 29 |
Machines à plusieurs rubans | 40 |
Copyright | |
12 other sections not shown
Other editions - View all
Common terms and phrases
accessible algorithme alphabet automate fini bijection borne inférieure borne supérieure chapitre ci-dessus classe de complexité classe DTIME(T(n codage code configuration initiale associée configuration terminale constructible d'ensemble d'états d'états Q définissable définition par récurrence demi-ruban Démonstration élément ensemble MT-décidable ensemble récursif entier entiers étapes de calcul états exemple existe une machine fonction d'Ackermann fonctions de complexité fonctions MT-calculables fonctions récursives formule booléenne formules du premier init l'addition l'algorithme associé l'arithmétique l'ensemble des formules l'ensemble des mots l'entier l'exponentiation l'indécidabilité lambda-calcul Lemme logiques du premier longueur M₁ machine de Turing modulo MT-semi-décidable N₁ notion NP-complet paramètres partout définie pointeur polynomial précédent premier ordre premier ruban problème de l'arrêt Proposition quelconque réalisation R relation binaire représentation resp résultat s'il existe second ruban semi-décide seulement signature simulation suivant suppose Supposons symbole de relation TH₁(N théorème d'incomplétude thèse de Church triplet troisième ruban type usuelles utilisant valeur vérifiant vraie y₁