Die Funktion zeigen =? ist unmöglich

Question

Hier ist ein Labor aus einem Informatikkurs im ersten Jahr, der in Schema unterrichtet wurde: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf

Am Ende des Labors präsentiert es im Grunde genommen das Anstaltproblem und zeigt, dass es unmöglich ist, durch Einführung der Funktion zu lösen diagonal, was definiert wird als:

(define (diagonal x)
  (cond
     [(halting? x x) (eternity 1)]
     [else true]))

Wo eternity ist ein nicht terminierendes Programm als definiert als (define (eternity x) (eternity x)). Was passiert, wenn Sie füttern? diagonal seine eigene Definition als Eingabe ...?

Das ist alles ziemlich Standard. Dann sagt das Labor:

Beantworten Sie die Frage, die am Ende von Übung 20.1.3 des Textes gestellt wurden, definitiv die Frage, mit der Interpretation, dass die Funktion =? Konsumiert zwei Listen, die den Code für die beiden Funktionen darstellen. Dies ist die Situation, in der Kirche in seinem Beweis berücksichtigt wird.

Das Kern davon ist also das function=? Nimmt zwei Eingänge. Jedes ist eine Liste, die die Definition einer Funktion darstellt, dh es ist eine Liste des Formulars (define (id args ...) body ...). Wir können davon ausgehen, dass beide Funktionen syntaktisch gültig sind und für alle Eingaben (ohne Laufzeitfehler) enden. function=? Gibt true zurück, wenn und nur dann, wenn die beiden Funktionen immer dasselbe Ergebnis zurückgeben, wenn dieselben Eingaben angegeben werden. Zum Beispiel,

(function=? '(define (foo x) (* 2 x)) 
            '(define (bar x) (+ x x))) ; should return #t

(function=? '(define (foo x) (+ x 1)) 
            '(define (bar x) (+ x 2))) ; should return #f

Jetzt, function=? ist offensichtlich unmöglich zu schreiben - die Herausforderung besteht darin beweisen es ist unmöglich. Ich habe eine Weile darüber nachgedacht, und die beste Lösung, die ich mir einfallen lassen konnte, ist Folgendes:

(define (disprove-function=? x)
  ((lambda (snip)
     (let ((self (list 'define '(disprove-function=? x)
                       (list snip (list 'quote snip)))))
       (if (function=? self '(define (id x) x))
           (list x)
           x)))
   '(lambda (snip) 
      (let ((self (list 'define '(disprove-function=? x)
                        (list snip (list 'quote snip)))))
        (if (function=? self '(define (id x) x))
            (list x)
            x)))))

Grundsätzlich, disprove-function=? Verwendet Standard -Quining -Techniken, um einen eigenen Quellcode (die Variable zu generieren self) und fragt dann function=? Wenn es der Identitätsfunktion entspricht. Wenn function=? sagt #f dann disprove-function=? wird sich immer wie die Identitätsfunktion verhalten. Widerspruch! Wenn function=? sagt #t dann disprove-function=? wird sich immer anders verhalten als Identität; Insbesondere wird es sich wie das verhalten list Funktion. Widerspruch! Daher, function=? kann nicht existieren. Qed.

Meine Frage lautet: Gibt es eine elegantere Möglichkeit, sich diesem Problem anzugehen? Meine Lösung scheint ... lang und hässlich. Nicht annähernd so schön wie das diagonal Funktion zum Nachweis, dass das Anhaltsproblem nicht löslich ist.

NB: Bitte geben Sie mir Antworten und keine Hinweise! Auch wenn dies eine Hausaufgabenfrage ist, ist es nicht mein Hausaufgaben Frage: Ich gehe nicht an diese Universität! Wie Sie aus dem Labor sehen können, befindet sich diese Frage außerdem unter dem Enhancements Kategorie und keine Noten wert. Auch wenn Sie mir nicht glauben, gibt es immer noch kein Problem damit, mir nur eine Antwort zu geben. Endlich schon ich schon haben Eine Lösung, die ich mir ziemlich sicher bin, ist recht; Ich habe mich nur gefragt, ob es eine gab besser Lösung.

Answer 1

Die Verwendung des Stoppproblems scheint die gute Lösung zu sein. Angenommen, Sie haben eine Funktion red das nimmt den Code einer Funktion (oder λ-Term) (oder eine ungyed -Funktion), reduziert einen Schritt (oder β-reDex) und gibt den Code der resultierenden Funktion zurück. Nehmen wir auch an, dass Sie eine Funktion haben normal Das heißt, wenn der Begriff in ist Normale Form.

In Turing Machines Sprache, red wäre die Berechnung von einem Schritt und normal würde wahr zurückkehren, wenn wir in einem endgültigen Zustand sind.

Lassen Sie uns die Berechnung von $ N $ Schritten simulieren und 43 $ anstelle von 1 $ $ zurückgeben, wenn wir das Ende der Berechnung erreichen:

(define (run t n)
  (if (= n 0) 1
    (if (normal t) 43
      (run (red t) (n-1)))))

Anschließend können wir entscheiden, ob die Ausführung eines Terms endet oder nicht:

(define (one x) 1)
(define (terminate t) (not (function=? (run t) one)))

Daraus können wir das übliche diagonale Argument verwenden:

(define (loop x) (loop x))
(define (f x) (if (terminate (code-of-application x (quote x))) (loop 0) 1)
(f code-of-f)

Wenn f endet auf code-of-f dann (terminate (code-of-application code-of-f (quote code-of-f)) wird zurückkehren true und dann f wird weitergehen code-of-f. Also sollte es schaufeln. Dann (terminate ...) sollte zurückkehren false und f wird enden code-of-f, Widerspruch.

Technische Raum: Man muss eine Basissprache definieren, die ausdrucksstark genug ist, um alles schreiben zu können, ist oben geschrieben. Du brauchst dann red und normal Das kann härter sein als man sich vorstellen kann. Sie benötigen auch die Standard -Quine -Techniken: quote Dies gibt angesichts des Code eines Terms einen Begriff zurück, der den Code des Begriffs darstellt, code-of-application a b ist einfach und selbsterklärend, und natürlich müssen Sie alles intern schreiben, um zu schreiben code-of-f.

Der Lambda-Calculus ist überraschend einfach und ausdrucksstark, all dies aufzuschreiben und ihre Richtigkeit zu beweisen, weshalb die Kirche sie verwendet hat, um es zu lösen Hilberts zehnte Problem, aber man kann es in vielen Sprachen tun, möglicherweise auf einfachere Weise, indem man sprachspezifische Quine-Tricks verwendet.