Tu ne te trompes pas mais ce n'est pas tout à fait la thèse de Church, c'est tout bonnement un théorème, dont la preuve est donnée par le fait qu'on peut écrire une machine de Turing qui interprète le lambda-calcul et un lambda-terme (un programme en lambda-calcul) qui simule une machine de Turing. La thèse de Church c'est le fait qu'on ne trouvera jamais d'« algorithme » (de procédé calculable) non exprimable par ces derniers modèles, et donc qu'on ne trouvera jamais de modèle plus expressif.
Si elles ont la même expressivité théorique, ces modèles ont quand même des usages différents en informatique scientifique : les machines de Turing sont un cadre commode pour parler de théorie de la complexité, parce qu'il est facile de quantifier le fonctionnement « mécanique » du calcul, avec une notion claire d'espace (la fameuse bande) et de temps (les déplacements de la tête de lecture/écriture), tandis que le lambda-calcul est plus abstrait et sert de fondement et de référence à toute la théorie des langages de programmation.
[^] # Re: Journal bookmark mais sujet intéressant
Posté par auve . En réponse au journal A Turing machine. Évalué à 10.
Si elles ont la même expressivité théorique, ces modèles ont quand même des usages différents en informatique scientifique : les machines de Turing sont un cadre commode pour parler de théorie de la complexité, parce qu'il est facile de quantifier le fonctionnement « mécanique » du calcul, avec une notion claire d'espace (la fameuse bande) et de temps (les déplacements de la tête de lecture/écriture), tandis que le lambda-calcul est plus abstrait et sert de fondement et de référence à toute la théorie des langages de programmation.