कोक

Question

में एकरमेन को परिभाषित करने में त्रुटि मैं कोक में एकरमेन-पीटर्स फ़ंक्शन को परिभाषित करने की कोशिश कर रहा हूं, और मुझे एक त्रुटि संदेश मिल रहा है जिसे मैं समझ नहीं पा रहा हूं। जैसा कि आप देख सकते हैं, मैं एक जोड़ी ab में एकरमेन के a, b तर्कों को पैकेजिंग कर रहा हूं; मैं तर्कों के लिए ऑर्डरिंग फ़ंक्शन को परिभाषित करने का आदेश प्रदान करता हूं। फिर मैं Function रूप का उपयोग एकरमेन को स्वयं परिभाषित करने के लिए करता हूं, इसे ab तर्क के लिए ऑर्डरिंग फ़ंक्शन प्रदान करता है।

Error: No such section variable or assumption: ack .

मुझे यकीन है कि क्या Coq परेशान है, लेकिन इंटरनेट खोज, मैंने पाया एक सुझाव वहाँ एक पुनरावर्ती का उपयोग कर के साथ एक समस्या हो सकती है नहीं कर रहा हूँ:

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. 

क्या मैं निम्न त्रुटि संदेश है फ़ंक्शन को ऑर्डरिंग या माप के साथ परिभाषित किया गया है, जहां रिकर्सिव कॉल एक मैच के भीतर होता है। हालांकि, अनुमानों का उपयोग fst और snd और if-then-else ने एक अलग त्रुटि संदेश उत्पन्न किया। क्या कोई सुझाव दे सकता है कि कोक में एकरमेन को कैसे परिभाषित किया जाए?

Answer 1

ऐसा लगता है कि Function इस समस्या को हल नहीं कर सकता है। हालांकि, इसके चचेरे भाई Program Fixpoint कर सकते हैं।

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. 

कुछ सरल परीक्षण का प्रदर्शन है कि हम ack साथ गणना कर सकता है:

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. 

अब हम एकरमैन-पीटर समारोह को परिभाषित कर सकते हैं:

चलो कुछ इलाज अच्छी तरह से foundedness पहले lemmas को परिभाषित करते हैं

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

Answer 2

आपको यह त्रुटि मिलती है क्योंकि आप इसे परिभाषित करते समय ack फ़ंक्शन का संदर्भ दे रहे हैं। स्वयं संदर्भ केवल Fixpoint एस (यानी रिकर्सिव फ़ंक्शंस) में अनुमत है, लेकिन समस्या यह है कि, जैसा कि आप शायद जानते हैं, कि एकरमेन फ़ंक्शन एक आदिम रिकर्सिव फ़ंक्शन नहीं है।

इस पर कुछ और जानकारी के लिए Coq'Art section 4.3.2.2 देखें।

तो इसे परिभाषित करने का एक वैकल्पिक तरीका दूसरे पुनरावर्ती कार्य को रेखांकित करना है जो दूसरे तर्क के लिए संरचनात्मक रूप से पुनरावर्ती है;

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

की तरह तो कुछ मैं सिर्फ Coq 8.4 के साथ अपने समारोह की कोशिश की, और त्रुटि थोड़ा अलग है:

Error: Nested recursive function are not allowed with Function 

मुझे लगता है कि ack के भीतर कॉल समस्या है, लेकिन मैं नहीं जानता कि क्यूं कर।

आशा इस में मदद करता है एक सा, वी

पुनश्च: हमेशा की तरह मैं परिभाषित Ack क्या तारों ने लिखा है एक आंतरिक fixpoint के साथ है।