Warum Call-by-Wert Bewertungsstrategie nicht Turing abgeschlossen?

Question

Ich lese einen Artikel über verschiedene Auswertestrategien (I Artikel in Wiki verlinkt, aber ich lese ein anderes nicht in englischer Sprache). Und er sagt, dass im Gegensatz zu call-by-name und call-by-need Strategien, call-by-value Strategie ist nicht Turing komplett .

Kann jemand bitte erklären, warum ist es so? Wenn es möglich ist, fügen Sie ein Beispiel pls.

Answer 1

Ich bestreiten den Anspruch in dem Artikel, den Sie gerade lesen. (Ich bin nicht dafür bezahlt, also werde ich ein suggestives Argument liefern, keinen Beweis.)

Es ist bekannt, dass, zumindest unter normaler Ordnung Reduktion (aka namentlich nennen), das reine Lambda-Kalkül ist Turing-vollständig. Aber wenn wir uns John Reynolds brech Papier Definitorische Interpreter für Geordnete Sprachen Programmierung, können wir sehen, dass Reynolds endlich nach Wert der Differenz zwischen Aufruf von Name und Rufnummer diskutiert. Ein wichtiger Teil des Arguments ist, dass, um eine richtige Unterscheidung zu machen, können wir ein Programm in Fortsetzung Umgehen Stil verwandeln. Die CPS-Transformation unterscheidet sich für Anruf von Bedarf und Call-by-Wert, aber die erhaltenen transformierten Begriffe können in jedem Stil ausgewertet werden.

das Argument Also hier kommt: ein Lambda-Kalkül Programm schreiben, das eine Turing-Maschine simuliert, CPS dann verwandeln sie die CBN-Transformation, und Sie können den resultierenden Code unter Verwendung einer CBV Bekämpfungsstrategie bewerten. Knall! Turing-vollständig.

In der Praxis, ich wette, Sie ein CBV-Programm schreiben können eine Turing-Maschine zu emulieren; es ist wahrscheinlich genug, um einen geeigneten Festpunkt combinator, wie T zum Beispiel zu wählen. (Je berühmter Y Combinator funktioniert nur unter einer Call-by-Name-Minderungsstrategie, das heißt, normale Ordnung Reduktion).

Hinweis: Ich habe nicht Lambda-Kalkül in Alter untersucht, und ich bin sicher, es gibt einige Details falsch in dem Argumente oben. Aber ich bin zuversichtlich, in der Substanz. Es wäre nicht das erste Mal sein, die ich etwas offensichtlich falsch in Online-Ressourcen über Programmiersprache Theorie entdeckt.

Answer 2

Ihre Frage sehr vielen Sinn nicht zu irgendeiner bestimmten Sprache ohne Bezug machen, aber ich werde mein Bestes, um Antwort in Bezug auf das Untypisierte Lambda-Kalkül versuchen.

Die Existenz eines Call-by-Wert Fixpunkt combinator (dh "Y Combinator") für das nicht typisierten Lambda-Kalkül scheint die grundlegende Behauptung zu widerlegen (siehe: Fixed Point Combinator ). Die Existenz eines solchen combinator bricht starke Normalisierung, was darauf hindeutet, dass es zumindest eine Sprache ist, die die Anwendungen eine Call-by-Wert Auswertestrategie Turing abgeschlossen ist.

Viel wahrscheinlicher die Turing-Vollständigkeit einer Sprache zu beeinflussen, ist die Existenz (oder fehlende) eine Art System. Zum Beispiel kann das einfach typisierten Lambda-Kalkül keinen festen Punkt combinator kodieren, und ist stark Normalisierung (das heißt alle gut getippt Bedingungen auf einen Wert zu reduzieren), jedoch ist dies gilt unabhängig von der verwendeten Bewertungsstrategie. Es ist vielmehr eine Folge des Typsystems.