Показывая функцию =? невозможно

Question

Вот лаборатория из курса по компьютерным наукам первого года, преподавая в схеме: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf

В конце лаборатории он в основном представляет проблему остановки и показывает, что ее невозможно решить, введя функцию diagonal, который определяется как:

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

Где eternity это не концевая программа, определяемая как (define (eternity x) (eternity x)). Анкет Что происходит, когда вы кормите diagonal его собственное определение как вход ...?

Это все довольно стандартные вещи. Затем лаборатория говорит:

Для реальной задачи определенно ответьте на вопрос, поставленного в конце упражнения 20.1.3 текста, с интерпретацией, которая функционирует =? Поглощает два списка, представляющие код для двух функций. Это ситуация Церковь, рассмотренная в его доказательстве.

Так что суть этого в том, что function=? берет два входа. Каждый из них является списком, который представляет определение функции, то есть это список формы (define (id args ...) body ...). Анкет Мы можем предположить, что обе функции являются синтаксически достоверными и будут прекращены для всех входов (без ошибок времени выполнения). function=? Возвращает true, если и только если две функции всегда будут возвращать один и тот же результат, когда будут предоставлены одинаковые входы. Например,

(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

В настоящее время, function=? явно невозможно написать - задача состоит в доказывать это невозможно. Я думал об этом некоторое время, и лучшее решение, которое я мог бы придумать, - это следующее:

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

В принципе, disprove-function=? использует стандартные методы Quining для генерации собственного исходного кода (переменная self), а затем спрашивает function=? Если это эквивалентно функции идентификации. Если function=? говорит #F, тогда disprove-function=? всегда будет вести себя как функция идентификации. Противоречие! Если function=? говорит #t, тогда disprove-function=? всегда будет вести себя иначе, чем идентичность; в частности, это будет вести себя как list функция Противоречие! Таким образом, function=? не может существовать. QED.

У меня вопрос: есть ли более элегантный способ подойти к этой проблеме? Мое решение кажется ... длинным и уродливым. Не так мило, как diagonal Функция для доказательства того, что проблема остановки неразрешима.

NB: Пожалуйста, дайте мне ответы, а не намеки! Несмотря на то, что это домашнее задание, это не мой Домашнее задание: я не хожу в этот университет! Кроме того, как вы можете видеть из лаборатории, этот вопрос под Enhancements Категория и не стоит отметить, поэтому даже если вы мне не верите, все еще нет проблем с тем, чтобы дать мне ответ. Наконец я уже имеют Решение, которое, я уверен, правильно; Мне просто было интересно, было ли лучше решение.

Answer 1

Использование проблемы остановки кажется хорошим решением. Предположим, у вас есть функция red который берет код функции (или λ-термин) (или нетипированная функция), уменьшает один шаг (или β-Redex) в нем и возвращает код полученной функции. Предположим, что у вас есть функция normal это говорит, что если термин находится в нормальная форма.

На языке машин Тьюринга, red было бы вычислением одного шага и normal вернется, когда мы находимся в конечном состоянии.

Давайте смоделируем вычисление шагов $ N $, возвращая 43 доллара $ вместо $ 1 $, если мы достигнем конца вычисления:

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

Тогда мы можем решить, будет ли завершение термина прекратить или нет:

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

Из этого мы можем использовать обычный диагональный аргумент:

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

Если f Заканчивается на code-of-f тогда (terminate (code-of-application code-of-f (quote code-of-f)) вернется true а потом f Будет пениться code-of-f. Анкет Так что это должно зацикливаться. затем (terminate ...) должен вернуться false а также f Завершится code-of-f, противоречие.

Технические детали: нужно определить базовый язык, который достаточно выразительен, чтобы писать все написано выше. Тогда вам нужно red а также normal что может быть сложнее, чем можно себе представить. Вам также нужны стандартные методы Quine: quote который, учитывая код термина, возвращает термин, представляющий код термина, code-of-application a b Легко и самоэкспланирует, и, конечно, вам нужно написать все выше, чтобы написать code-of-f.

Lambda-Calculus на удивление прост и выразительна для того, чтобы записать все это вниз и доказать ее правильность, поэтому Церковь использовала его для решения Десятая проблема Гильберта, но можно сделать это на многих языках, возможно, более простым способом, используя специфичные для языковых трюки.