Mostrando i = funzione? è impossibile

Question

Ecco un laboratorio da un corso di informatica al primo anno, ha insegnato nello Schema: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf

Al termine del laboratorio, presenta sostanzialmente il problema della terminazione, e dimostra che è impossibile risolvere introducendo la funzione diagonal, che è definito come:

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

Dove eternity è un programma non fatale definito come (define (eternity x) (eternity x)). Cosa succede quando si alimenta diagonal la propria definizione come input ...?

Questa è tutta roba abbastanza standard. Poi, il laboratorio dice:

Per una vera sfida, de fi nitivamente rispondere alla domanda posta alla fine di Esercizio 20.1.3 del il testo, con l'interpretazione che la funzione =? consuma due liste che rappresentano il codice per i due funzioni. Questa è la Chiesa situazione considerata nella sua prova.

Quindi, l'essenza di esso è che function=? prende due ingressi. Ciascuno è un elenco che rappresenta la definizione di una funzione, cioè esso è un elenco della forma (define (id args ...) body ...). Possiamo supporre che entrambe le funzioni sono sintatticamente valido e Vi terminare per tutti gli ingressi (senza errori runtime). restituisce function=? vero se e solo se le due funzioni restituiranno sempre lo stesso risultato quando attribuiti gli stessi ingressi. Ad esempio,

(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

Ora, function=? è ovviamente impossibile da scrivere - la sfida è quella di dimostrare è impossibile. Ho pensato a questo per un po ', e la soluzione migliore che ho potuto venire con è la seguente:

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

Fondamentalmente, disprove-function=? utilizza tecniche quining standard per generare il proprio codice sorgente (variabile self), e poi chiede function=? se è equivalente alla funzione identità. Se function=? dice #f, quindi disprove-function=? sarà sempre comportarsi come la funzione identità. Contraddizione! Se function=? dice #t, quindi disprove-function=? sarà sempre comportarsi in modo diverso dall'identità; in particolare, si comporterà come la funzione list. Contraddizione! Così, function=? non può esistere. QED.

La mia domanda è: esiste un modo più elegante per affrontare questo problema? La mia soluzione sembra ... lungo e brutto. Non altrettanto bello come la funzione diagonal per dimostrare che il problema della terminazione è irrisolvibile.

NB: Si prega di dare mi risponde e non i suggerimenti! Anche se questa è una domanda compiti a casa, non è il mio domanda compiti a casa: io non vado a questa università! Inoltre, come si può vedere dal laboratorio, questa domanda è sotto la categoria Enhancements e non è un valore di segni, quindi, anche se non mi credete, non v'è ancora alcun problema con me solo dare una risposta. Infine, ho già sono di una soluzione, che io sono abbastanza sicuro è giusto; Mi stavo chiedendo se ci fosse un migliore soluzione.

Answer 1

Utilizzando il problema della terminazione sembra la buona soluzione. Supponiamo di avere una funzione red che prende il codice di una funzione (o ? termine) (o una funzione tipizzato), riduce un passo (o ß-redex ) in esso e restituisce il codice della funzione risultante. Supponiamo inoltre di avere una funzione normal che dice che se il termine è in forma normale .

In Turing macchine linguaggio, red sarebbe il calcolo di un passo e normal restituirà vero quando siamo in uno stato finale.

simulare Let il calcolo di $ n $ passi, tornando $ 43 $ invece di $ 1 $ se si arriva alla fine del calcolo:

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

Poi si può decidere se l'esecuzione di un mandato terminerà o meno:

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

Da che siamo in grado di utilizzare il solito argomento diagonale:

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

Se termina f su code-of-f poi (terminate (code-of-application code-of-f (quote code-of-f)) torneranno true e ciclo volontà poi f su code-of-f. Così dovrebbe loop. Poi (terminate ...) deve restituire false e f terminerà il code-of-f, contraddizione.

Aspetti tecnici: una necessità di definire una lingua di base che è abbastanza espressiva per essere in grado di scrivere tutto è scritto sopra. È quindi necessario red e normal che può essere più difficile di quanto si possa immaginare. È necessario anche le tecniche Quine standard: quote che, dato il codice di un termine, restituisce un termine che rappresenta il codice del termine, code-of-application a b è facile e intuitivo, e, naturalmente, è necessario tutto ciò scrittura sopra internamente per code-of-f scrittura.

Il lambda calcolo è sorprendentemente semplice ed espressivo ad entrambi scrivere tutto questo in giù e per dimostrare la sua correttezza, che è il motivo per cui Chiesa utilizzato per risolvere di Hilbert problema decimo , ma si può fare in un sacco di lingue, possibilmente in modo più semplice, usando i trucchi della lingua specifica Quine.