La thèse de Church-Turing fait référence au concept d'une méthode efficace, systématique ou mécanique en logique, en mathématiques et en informatique. Elle est formulée comme une description du concept intuitif de calculabilité et, par rapport aux fonctions récursives générales, est plus souvent appelée thèse de Church. Il fait également référence à la théorie des fonctions calculables par ordinateur. La thèse est apparue dans les années 1930, alors que les ordinateurs eux-mêmes n'existaient pas encore. Il a ensuite été nommé d'après le mathématicien américain Alonso Church et son collègue britannique Alan Turing.
Efficacité de la méthode pour obtenir le résultat
Le premier appareil qui ressemblait à un ordinateur moderne était le Bombie, une machine créée par le mathématicien anglais Alan Turing. Il a été utilisé pour déchiffrer les messages allemands pendant la Seconde Guerre mondiale. Mais pour sa thèse et la formalisation du concept d'algorithme, il a utilisé des machines abstraites, plus tard appelées machines de Turing. Thèse présenteintérêt tant pour les mathématiciens que pour les programmeurs, puisque cette idée a inspiré les créateurs des premiers ordinateurs.
Dans la théorie de la calculabilité, la thèse de Church-Turing est également connue sous le nom de conjecture sur la nature des fonctions calculables. Il stipule que pour toute fonction algorithmiquement calculable sur des nombres naturels, il existe une machine de Turing capable de la calculer. Ou, en d'autres termes, il existe un algorithme adapté. Un exemple bien connu de l'efficacité de cette méthode est le test de la table de vérité pour tester la tautologie.
Un moyen d'obtenir n'importe quel résultat souhaité est appelé "efficace", "systématique" ou "mécanique" si:
- La méthode est spécifiée en termes d'un nombre fini d'instructions exactes, chaque instruction est exprimée en utilisant un nombre fini de caractères.
- Il fonctionnera sans erreur, produira le résultat souhaité en un certain nombre d'étapes.
- La méthode peut être exécutée par un humain sans aide avec n'importe quel équipement autre que du papier et un crayon
- Cela ne nécessite pas de compréhension, d'intuition ou d'ingéniosité de la part de la personne qui exécute l'action
Plus tôt en mathématiques, le terme informel "effectivement calculable" était utilisé pour désigner les fonctions qui peuvent être calculées avec un crayon et du papier. Mais la notion même de calculabilité algorithmique était plus intuitive que tout ce qui était concret. Maintenant, il était caractérisé par une fonction à argument naturel, pour laquelle il existe un algorithme de calcul. L'une des réalisations d'Alan Turing a étéreprésentation d'un prédicat formellement exact, à l'aide duquel il serait possible de remplacer l'informel, si la condition d'efficacité de la méthode est utilisée. Church a fait la même découverte.
Concepts de base des fonctions récursives
Le changement de prédicats de Turing, à première vue, semblait différent de celui proposé par son collègue. Mais du coup, elles se sont avérées équivalentes, en ce sens que chacune d'elles sélectionne le même ensemble de fonctions mathématiques. La thèse de Church-Turing est l'affirmation que cet ensemble contient toute fonction dont les valeurs peuvent être obtenues par une méthode qui satisfait les conditions d'efficacité. Il y avait une autre différence entre les deux découvertes. C'est que Church ne considérait que des exemples d'entiers positifs, tandis que Turing décrivait son travail comme couvrant des fonctions calculables avec une variable intégrale ou réelle.
Fonctions récursives communes
La formulation originale de Church indique que le calcul peut être effectué en utilisant le λ-calcul. Cela équivaut à utiliser des fonctions récursives génériques. La thèse de Church-Turing couvre plus de types de calculs qu'on ne le pensait à l'origine. Par exemple, liés aux automates cellulaires, aux combinateurs, aux machines d'enregistrement et aux systèmes de substitution. En 1933, les mathématiciens Kurt Gödel et Jacques Herbrand ont créé une définition formelle d'une classe appelée fonctions récursives générales. Il utilise des fonctions où plus d'un argument est possible.
Créer une méthodeλ-calcul
En 1936, Alonso Church a créé une méthode de détermination appelée le λ-calcul. Il était associé aux nombres naturels. Dans le λ-calcul, le scientifique a déterminé leur codage. En conséquence, ils sont appelés numéros d'église. Une fonction basée sur des nombres naturels était appelée λ-calculable. Il y avait une autre définition. La fonction issue de la thèse de Church est dite λ-calculable sous deux conditions. La première ressemblait à ceci: si elle était calculée sur les éléments de l'Église, et la deuxième condition était la possibilité d'être représentée par un membre du λ-calcul.
Toujours en 1936, avant d'étudier les travaux de son collègue, Turing créa un modèle théorique pour les machines abstraites qui portent désormais son nom. Ils pourraient effectuer des calculs en manipulant les caractères sur la bande. Cela s'applique également à d'autres activités mathématiques trouvées dans l'informatique théorique, telles que l'informatique probabiliste quantique. La fonction de la thèse de Church n'a été étayée que plus tard à l'aide d'une machine de Turing. Initialement, ils se sont appuyés sur le λ-calcul.
Calculabilité des fonctions
Lorsque les nombres naturels sont codés de manière appropriée sous forme de séquences de caractères, une fonction sur les nombres naturels est dite calculable par Turing si la machine abstraite a trouvé l'algorithme requis et a imprimé cette fonction sur bande. Un tel appareil, qui n'existait pas dans les années 1930, serait à l'avenir considéré comme un ordinateur. La machine abstraite de Turing et la thèse de Church annonçaient une ère de développementappareils informatiques. Il a été prouvé que les classes de fonctions formellement définies par les deux scientifiques coïncident. Par conséquent, en conséquence, les deux déclarations ont été combinées en une seule. Les fonctions de calcul et la thèse de Church ont également eu une forte influence sur le concept de calculabilité. Ils sont également devenus un outil important pour la logique mathématique et la théorie de la preuve.
Justification et problèmes de la méthode
Il y a des points de vue contradictoires sur la thèse. De nombreuses preuves ont été recueillies pour "l'hypothèse de travail" proposée par Church et Turing en 1936. Mais toutes les méthodes ou opérations connues pour découvrir de nouvelles fonctions effectivement calculables à partir de fonctions données étaient liées à des méthodes de construction de machines, qui n'existaient pas alors. Pour prouver la thèse de Church-Turing, on part du fait que tout modèle réaliste de calcul est équivalent.
En raison de la variété des différentes analyses, cela est généralement considéré comme une preuve particulièrement solide. Toutes les tentatives pour définir plus précisément la notion intuitive de fonction effectivement calculable se sont avérées équivalentes. Toutes les analyses qui ont été proposées se sont avérées distinguer la même classe de fonctions, à savoir celles qui sont calculables par les machines de Turing. Mais certains modèles de calcul se sont avérés plus efficaces en termes de temps et d'utilisation de la mémoire pour différentes tâches. Plus tard, il a été noté que les concepts de base des fonctions récursives et la thèse de Church sont plutôt hypothétiques.
Thèse M
Il est important de faire la distinction entre la thèse de Turing et l'affirmation selon laquelle tout ce qui peut être calculé par un appareil informatique peut être calculé par sa machine. La deuxième option a sa propre définition. Gandhi appelle la deuxième phrase "Thèse M". Cela ressemble à ceci: "Tout ce qui peut être calculé par un appareil peut être calculé par une machine de Turing." Au sens étroit de la thèse, c'est une proposition empirique dont la valeur de vérité est inconnue. La thèse de Turing et la "thèse M" sont parfois confondues. La deuxième version est largement incorrecte. Diverses machines conditionnelles ont été décrites qui peuvent calculer des fonctions qui ne sont pas calculables par Turing. Il est important de noter que la première thèse n'implique pas la seconde, mais est cohérente avec sa fausseté.
Implication inverse de la thèse
Dans la théorie de la calculabilité, la thèse de Church est utilisée comme une description de la notion de calculabilité par une classe de fonctions récursives générales. L'Américain Stephen Kleene a donné une formulation plus générale. Il a appelé partiellement récursives toutes les fonctions partielles calculables par des algorithmes.
L'implication inverse est communément appelée la thèse inverse de Church. Elle réside dans le fait que toute fonction récursive d'entiers positifs est efficacement évaluée. Au sens étroit, une thèse dénote simplement une telle possibilité. Et dans un sens plus large, cela fait abstraction de la question de savoir si cette machine conditionnelle peut exister en elle.
Ordinateurs quantiques
Les concepts de fonctions calculables et la thèse de Church sont devenus une découverte importante pour les mathématiques, la théorie des machines et de nombreuses autres sciences. Mais la technologie a beaucoup changé et continue de s'améliorer. On suppose que les ordinateurs quantiques peuvent effectuer de nombreuses tâches courantes en moins de temps que les ordinateurs modernes. Mais des questions subsistent, comme le problème de l'arrêt. Un ordinateur quantique ne peut pas y répondre. Et, selon la thèse de Church-Turing, aucun autre appareil informatique non plus.
