La thèse de Church-Turing s'applique-t-elle également à l'intelligence artificielle?

8

Selon la thèse de Church-Turing, il est impossible de concevoir un algorithme pour décider du problème d'arrêt.

Le mot algorithme dans ce contexte inclut-il ou non l'intelligence artificielle, c'est-à-dire que la thèse de Church-Turing s'applique-t-elle également à l'intelligence artificielle?

Est-il possible de concevoir un système de renseignement à l'avenir pour décider de ce problème, ou, par la thèse de Church-Turing, aucune IA ne pourra également décider du problème d'arrêt?

computability artificial-intelligence halting-problem church-turing-thesis M ama D
la source
2
Il est peu probable qu'un système d'IA puisse décider quoi que ce soit (au sens formel et déterministe), mais s'il le pouvait, il violerait certainement la thèse de Church-Turing ou l'indécidabilité du problème de l'arrêt. (Le dernier si c'est écrit dans une langue complète de Turing, le premier sinon.)
Raphael
Pourquoi pensez-vous qu'il est possible que l'intelligence artificielle ne soit pas couverte (ou concernée) par la thèse de Charch-Turing?
babou
@babou car il inclut le non déterminisme, l'apprentissage, etc. Il y a des problèmes non résolubles que l'IA nous donne une très bonne approximation de la solution.
M ama D
4
@Drupalist: mais la décidabilité d'un problème signifie simplement qu'il existe un algorithme tel que pour toute entrée donnée de l'espace d'entrée du problème, la sortie correcte sera produite. Alors oui, un algorithme d'IA (ou tout autre algorithme) pourrait donner de bonnes approximations pour le problème d'arrêt, mais cela n'entraînera pas de décidabilité.
Roy O.

Réponses:

18

La thèse de Church-Turing dit que la notion informelle d'un algorithme comme une séquence d'instructions coïncide avec les machines de Turing. De manière équivalente, il dit que tout modèle de calcul raisonnable a la même puissance que les machines de Turing.

Une intelligence artificielle est un programme informatique, c'est-à-dire un algorithme. Si la thèse de Church-Turing tient, alors vous pouvez implémenter cet algorithme sur une machine de Turing. Puisque les machines de Turing ne peuvent pas décider de leur propre problème d'arrêt, il s'ensuit que, selon la thèse de Church-Turing, les intelligences artificielles ne peuvent pas décider du problème d'arrêt des machines de Turing.

David Richerby
la source
D'un autre côté, si l'IA a été écrite sur une sorte d'ordinateur analogique ou sur un circuit infini non uniforme, le problème de l'arrêt des machines de Turing est de retour.
DanielV
3
@DanielV Un circuit infini non uniforme n'aide pas. S'il a une description calculable, il ne peut pas résoudre le problème d'arrêt; s'il n'a pas de description calculable, vous ne pouvez pas le construire.
David Richerby
Vous ne pouvez pas le construire avec une machine de Turing. Cela ne signifie pas que cela ne signifie pas que son existence est plus paradoxale que 2 points étant à une distance arbitraire.
DanielV
2
@DanielV Comment allez-vous dire à votre électricien quelles portes mettre dans le ne circuit s'il n'y a pas de description calculable?
David Richerby
1
@DanielV Il y a des problèmes que vous ne pouvez tout simplement pas calculer. Vous devez être en mesure de décider quand vous avez résolu le problème, ainsi que la réponse. Dans le cas du problème d'arrêt, il n'y a aucun moyen de déterminer que vous avez résolu le problème, et encore moins de trouver la réponse.
Plus clair le