Lỗi khi xác định Ackermann trong Coq

Question

Tôi đang cố xác định hàm Ackermann-Peters trong Coq và tôi nhận được thông báo lỗi mà tôi không hiểu. Như bạn có thể thấy, tôi đang đóng gói các đối số a, b của Ackermann theo cặp ab; Tôi cung cấp một thứ tự xác định một hàm đặt hàng cho các đối số. Sau đó, tôi sử dụng biểu mẫu Function để xác định chính Ackermann, cung cấp cho nó hàm đặt hàng cho đối số ab.

Require Import Recdef.  
Definition ack_ordering (ab1 ab2 : nat * nat) := 
    match (ab1, ab2) with 
    |((a1, b1), (a2, b2)) => 
     (a1 > a2) \/ ((a1 = a2) /\ (b1 > b2)) 
    end. 
Function ack (ab : nat * nat) {wf ack_ordering} : nat := 
match ab with 
| (0, b) => b + 1 
| (a, 0) => ack (a-1, 1) 
| (a, b) => ack (a-1, ack (a, b-1)) 
end. 

Những gì tôi nhận được là thông báo lỗi sau:

Error: No such section variable or assumption: ack .

Tôi không chắc chắn những gì phiền Coq, nhưng tìm kiếm trên internet, tôi thấy một gợi ý có thể có vấn đề với việc sử dụng một đệ quy hàm được định nghĩa với một thứ tự hoặc một số đo, trong đó cuộc gọi đệ quy xuất hiện trong một trận đấu. Tuy nhiên, sử dụng các dự báo fst và snd và một if-then-else đã tạo một thông báo lỗi khác. Ai đó có thể xin đề nghị làm thế nào để xác định Ackermann trong Coq?

Answer 1

Có vẻ như Function không thể giải quyết được sự cố này. Tuy nhiên, anh em họ của nó Program Fixpoint có thể.

Hãy xác định một số bổ đề điều trị tốt foundedness đầu tiên:

Require Import Coq.Program.Wf. 
Require Import Coq.Arith.Arith. 

Definition lexicographic_ordering (ab1 ab2 : nat * nat) : Prop := 
    match ab1, ab2 with 
    | (a1, b1), (a2, b2) => 
     (a1 < a2) \/ ((a1 = a2) /\ (b1 < b2)) 
    end. 

(* this is defined in stdlib, but unfortunately it is opaque *) 
Lemma lt_wf_ind : 
    forall n (P:nat -> Prop), (forall n, (forall m, m < n -> P m) -> P n) -> P n. 
Proof. intro p; intros; elim (lt_wf p); auto with arith. Defined. 

(* this is defined in stdlib, but unfortunately it is opaque too *) 
Lemma lt_wf_double_ind : 
    forall P:nat -> nat -> Prop, 
    (forall n m, 
     (forall p (q:nat), p < n -> P p q) -> 
     (forall p, p < m -> P n p) -> P n m) -> forall n m, P n m. 
Proof. 
    intros P Hrec p. pattern p. apply lt_wf_ind. 
    intros n H q. pattern q. apply lt_wf_ind. auto. 
Defined. 

Lemma lexicographic_ordering_wf : well_founded lexicographic_ordering. 
Proof. 
    intros (a, b); pattern a, b; apply lt_wf_double_ind. 
    intros m n H1 H2. 
    constructor; intros (m', n') [G | [-> G]]. 
    - now apply H1. 
    - now apply H2. 
Defined. 

Bây giờ chúng ta có thể xác định chức năng Ackermann-Péter:

Program Fixpoint ack (ab : nat * nat) {wf lexicographic_ordering ab} : nat := 
    match ab with 
    | (0, b) => b + 1 
    | (S a, 0) => ack (a, 1) 
    | (S a, S b) => ack (a, ack (S a, b)) 
    end. 
Next Obligation. 
    inversion Heq_ab; subst. left; auto. Defined. 
Next Obligation. 
    apply lexicographic_ordering_wf. Defined. 

Một số xét nghiệm đơn giản chứng minh rằng chúng ta có thể tính toán với ack:

Example test1 : ack (1, 2) = 4 := eq_refl. 
Example test2 : ack (3, 4) = 125 := eq_refl. (* this may take several seconds *) 

Answer 2

Bạn nhận được lỗi này vì bạn đang tham chiếu hàm ack trong khi xác định. Tự tham chiếu chỉ được phép trong Fixpoint s (nghĩa là các hàm đệ quy) nhưng vấn đề là, như bạn có thể biết, rằng hàm Ackermann không phải là một hàm đệ quy nguyên thủy.

Xem Coq'Art section 4.3.2.2 để biết thêm thông tin về điều này.

Vì vậy, một cách khác để xác định nó là bằng cách nội tuyến một hàm đệ quy thứ hai có cấu trúc đệ quy cho đối số thứ hai; nên cái gì như

Fixpoint ack (n m : nat) : nat := 
    match n with 
    | O => S m 
    | S p => let fix ackn (m : nat) := 
       match m with 
       | O => ack p 1 
       | S q => ack p (ackn q) 
       end 
      in ackn m 
    end. 

Answer 3

Tôi chỉ cố gắng chức năng của bạn với Coq 8.4, và lỗi này là hơi khác nhau:

Error: Nested recursive function are not allowed with Function 

Tôi đoán các cuộc gọi nội để ack là vấn đề, nhưng tôi không biết tại sao.

Hope this helps một chút, V.

PS: Cách thông thường tôi xác định Ack là những gì dây đã viết, với một fixpoint bên trong.