Affichage la fonction =? est impossible

Question

Voici un laboratoire à partir d'une première année de cours d'informatique, a enseigné dans le schéma: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf

A la fin du laboratoire, il présente essentiellement le problème de l'arrêt, et montre qu'il est impossible de résoudre en introduisant la fonction diagonal, qui est défini comme suit:

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

Où eternity est un programme de non-terminaison définie comme (define (eternity x) (eternity x)). Qu'est-ce qui se passe quand vous nourrissez diagonal sa propre définition comme entrée ...?

Ceci est tous les trucs assez standard. Ensuite, le laboratoire dit:

Pour un véritable défi, dé fi nitivement répondre à la question posée à la fin de l'exercice 20.1.3 du texte, l'interprétation que la fonction =? consomme deux listes représentant le code pour les deux les fonctions. Ceci est l'Eglise de la situation considérée dans sa preuve.

l'essentiel de ce que function=? prend deux entrées. Chacun d'eux est une liste, qui représente la définition d'une fonction, à savoir qu'il est une liste de la forme (define (id args ...) body ...). On peut supposer que les deux fonctions sont syntaxiquement valides et supprimerons pour toutes les entrées (sans erreurs d'exécution). retours function=? vrai si et seulement si les deux fonctions renvoient toujours le même résultat quand on donne les mêmes entrées. Par exemple,

(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

Maintenant, function=? est évidemment impossible d'écrire - le défi consiste à prouver il est impossible. Je pensais à ce sujet pendant un certain temps, et la meilleure solution que je pourrais trouver est la suivante:

(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)))))

En gros, disprove-function=? utilise des techniques standard de quining pour générer son propre code source (la self variable), et demande alors function=? si elle est équivalente à la fonction d'identité. Si function=? dit #f, alors disprove-function=? toujours se comporter comme la fonction d'identité. Contradiction! Si function=? dit #t, alors disprove-function=? se comportera toujours différemment de l'identité; en particulier, il se comporte comme la fonction list. Contradiction! Ainsi, function=? ne peut exister. QED.

Ma question est: est-il une façon plus élégante d'aborder ce problème? Ma solution semble ... long et laid. Pas presque aussi belle que la fonction diagonal pour prouver que le problème est insoluble arrêt.

NB: S'il vous plaît me donner des réponses et non des conseils! Bien que ce soit une question de devoirs, il n'est pas my question de devoirs: Je ne vais pas à cette université! En outre, comme vous pouvez le voir dans le laboratoire, cette question est dans la catégorie Enhancements et ne sont pas des marques d'une valeur, même si vous ne me croyez pas, il n'y a toujours pas de problème avec juste me donner une réponse. Enfin, je l'ai déjà Vous une solution, que je suis assez sûr est droit; Je me demandais s'il y avait une meilleure solution .

Answer 1

En utilisant le problème de l'arrêt semble être la bonne solution. Supposons que vous ayez une red fonction qui prend le code d'une fonction (ou ? terme ) (ou une fonction non typée), réduit une étape (ou ß-redex ) en elle et retourne le code de la fonction résultante. Supposons également que vous avez une normal fonction qui indique si le terme est sous forme normale .

Dans le langage des machines de Turing, red serait le calcul d'une étape et normal retournerait vrai quand nous sommes dans un état final.

Soit s Simuler le calcul de $ n étapes $, retour $ 43 $ au lieu de 1 $ si nous arrivons à la fin du calcul:

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

Ensuite, nous pouvons décider si l'exécution d'un mandat prendra fin ou non:

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

A partir de ce que nous pouvons utiliser l'argument de la diagonale habituelle:

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

Si f sur code-of-f se termine alors (terminate (code-of-application code-of-f (quote code-of-f)) retourneront true puis boucle f de volonté code-of-f. Donc, il doit passer en boucle. Alors (terminate ...) devrait revenir false et f prendra fin le code-of-f, contradiction.

Aspects techniques: un besoin de définir un langage de base qui est suffisamment expressif pour pouvoir écrire tout ce qui est écrit ci-dessus. Vous avez alors besoin red et normal qui peut être plus difficile que l'on peut imaginer. Vous devez également les techniques standard de Quine: quote qui, étant donné le code d'un terme, renvoie un terme représentant le code du terme, code-of-application a b est facile et explicite, et bien sûr, vous devez tout d'écriture ci-dessus en interne pour écrire code-of-f.

Le lambda-calcul est étonnamment simple et expressif à la fois écrire tout cela vers le bas et de prouver son exactitude, ce qui explique pourquoi l'Eglise a utilisé pour résoudre