Pourquoi la stratégie d'évaluation appel par valeur n'est pas complète Turing?

Question

Je lis un article sur les différentes href="http://en.wikipedia.org/wiki/Evaluation_strategy" (article I liés wiki, mais je lis un autre pas en anglais). Et il est dit que, contrairement aux stratégies de call-by-name et call-by-need, la stratégie de call-by-value est pas complète Turing .

Quelqu'un peut-il expliquer, s'il vous plaît, pourquoi est-il si? S'il est possible, ajoutez un exemple Pls.

Answer 1

Je conteste la demande dans l'article que vous lisez. (Je ne suis pas payé pour cela, donc je vais donner un argument suggestif, pas une preuve.)

Il est bien connu que, au moins en réduction ordre normal (appel aka par nom), le calcul pur lambda est Turing-complet. Mais si l'on regarde un article fondateur de John Reynolds définitionnelle Interprètes car, nous pouvons voir que Reynolds discute longuement la différence entre l'appel par nom et par valeur d'ordre supérieur Programmation langues. Une partie essentielle de l'argument est que, pour faire une distinction appropriée, nous pouvons transformer un programme en de style passage de continuation . La CPS transformation est différente pour les appels par le besoin et par valeur, mais les termes transformés obtenus peuvent être évalués soit dans le style.

est donc ici l'argument: écrire un programme lambda-calcul qui simule une machine de Turing, puis la transformer en utilisant la Présélection transformer la CBN, et vous pouvez évaluer le code résultant en utilisant une stratégie de réduction CBV. Coup! Turing-complet.

Dans la pratique, je parie que vous pouvez écrire un programme CBV pour émuler une machine de Turing; il est probablement suffisant pour choisir un combinateur approprié à point fixe, comme T par exemple. (Plus célèbre Y Combinator ne fonctionne que lors d'un appel par nom stratégie de réduction, à savoir, la réduction d'ordre normal.)

Disclaimer: Je n'ai pas étudié le calcul lambda dans les âges, et je suis sûr qu'il ya plusieurs détails faux dans l'argument ci-dessus. Mais je suis confiant dans la substance. Il ne serait pas la première fois que je remarquai quelque chose de mal à une manière flagrante des ressources en ligne sur la théorie de la langue de programmation.

Answer 2

Votre question ne fait pas beaucoup de sens sans référence à un langage spécifique, mais je vais essayer de mon mieux pour répondre par rapport au calcul typées Lambda.

L'existence d'un appel par valeur en virgule fixe combinateur (ie « Y combinateur ») pour le calcul non typé lambda semble infirmer la revendication base (voir: point fixe Combinator ). L'existence d'un tel casse combinateur de normalisation forte, ce qui suggère qu'il y ait au moins une langue qui est Türing complet qui utilise un appel par valeur stratégie d'évaluation.

Beaucoup plus susceptibles d'influer sur le turation-intégralité d'une langue est l'existence (ou l'absence) d'un système de type. Par exemple, le calcul lambda simplement typé ne peut pas coder un point fixe Combinator, et est fortement normalisant (à savoir tous les termes bien typés réduisent à une valeur), cependant, cela est vrai quelle que soit la stratégie d'évaluation employée. Au contraire, elle est une conséquence du système de type.