Principe de Church-Turing-Deutsch

Cet article est une ébauche concernant l’informatique et la physique quantique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Le principe de Church-Turing-Deutsch est une forme plus forte de la thèse de Church (ou thèse de Church-Turing) qui a été formulée par David Deutsch en 1985. Selon ce principe, un calculateur universel peut simuler tous les processus physiques.

Tel qu'il a été énoncé par Deutsch, la formulation est la suivante :

« Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means^[1]. »

« N'importe quel système physique fini réalisable peut être parfaitement simulé par un modèle de machine calculatrice opérant par des moyens finis. »

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Church–Turing–Deutsch principle » (voir la liste des auteurs).

↑ David Deutsch, « Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer », Proceedings of the Royal Society, 1985, Series A, 400, pp 97-117

Articles connexes

v · m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique