Λ-पथरी पर मोनोग्राफ का सारांश

यह पाठ λ-पथरी (H. Barendregt, "Lambda पथरी। इसका वाक्यविन्यास और शब्दार्थ") पर शास्त्रीय मोनोग्राफ का एक अत्यंत संक्षिप्त संकलन है, जिसका अनुवाद अंग्रेजी में G. S. Muzichev, Moscow, "Mir" द्वारा संपादित G. E. Mints द्वारा किया गया है। , 1985)। यह उन सभी के लिए दिलचस्प हो सकता है जिन्होंने इस विषय का एक व्यवस्थित अध्ययन करने की योजना बनाई थी, पहले से ही आम तौर पर खुद को इससे परिचित कराया, लेकिन मुख्य मोनोग्राफ की जटिल संरचना, परिभाषाओं और मुख्य परिणामों के कारण इसे स्थगित कर दिया, बल्कि बल्कि बिखरे हुए हैं। यहां हम प्रेजेंटेशन बनाने की कोशिश करेंगे, इसके विपरीत, बिल्कुल रैखिक, और, ज़ाहिर है, अतुलनीय रूप से कम, अनावश्यक परिभाषाओं और उदाहरणों से परहेज करते हुए, और आवश्यक शब्दावली, अंकन और बयानों पर ध्यान केंद्रित करते हुए, जो मूल पाठ के करीब सेट किए गए हैं। हम सिस्टम λβη को परिभाषित करके शुरू करते हैं, अर्थात्, शास्त्रीय टाइपलेस एक्सट्रूज़न λ-पथरी। फिर हम कॉम्बिनेटरियल लॉजिक, फिक्स्ड-पॉइंट प्रमेय और सिंटैक्टिक शुगर की ओर बढ़ते हैं। अंत में, सिनोप्सिस का अंतिम भाग इस प्रणाली की अभिव्यक्तियों पर एक टोपोलॉजी का निर्माण है, जिसे स्पष्ट विरोधाभास को समझाने के लिए डिज़ाइन किया गया है: अभिव्यक्तियों के समुच्चय के मानचित्रण स्वयं इस समुच्चय में निहित होते हैं जब यह गणनीय होता है। वास्तव में, सेट को उचित टोपोलॉजी के साथ संपन्न किया जाता है जिसमें भाव निरंतर मैपिंग होते हैं।

सिद्धांत

Λ- भाव के समुच्चय का निर्माण क्रियात्मक रूप से चर से किया जाता है

x, y, z ... ... ...

सार का उपयोग करना

M Λ Λ ⇒ λx.M ∈ Λ

और अनुप्रयोग

M, N ∈ ∈ ⇒ MN N ∈,

जबकि आवेदन बाएँ-सहयोगी है:

(एम) M एम, एमएनपी ≣ (एमएन) पी।

प्रतिवर्ती सकर्मक संबंध lex lex N का अर्थ है कि M , अभिव्यक्ति N का उप योग है :

एम M एम ⊂ λx.M;
एम M एमएन ⊂ एन;
एम ⊂ एन ⊂ एन ⊂ पी ⇒ एम। पी।

FV (M) M में मुक्त चर का समूह है:

FV (x) x {x};
FV (λx.M) V FV (M)} {x};
FV (MN) V FV (M) (FV (N)।

चर जो मुक्त नहीं हैं उन्हें बाध्य कहा जाता है और उन्हें दूसरे चर से बदला जा सकता है (इस तरह के परिवर्तन को α- रूपांतरण कहा जाता है):

y .M FV (M) ⇒ λx.M λ λy.M [x: = y], जहां M [x: = N] प्रतिस्थापन का परिणाम है:

x [x: = P] P पी;
y [x: = P] P y;
(λx.M) [x: = P] .M λx.M;
(λy.M) [x: = P] .M λy.M [x: = P];
(MN) [x: = P]) M [x: = P] N [x: = P]।

चौथे पैराग्राफ में, विशेष रूप से "x y y और y V FV (P)" स्थिति को निर्धारित करना आवश्यक नहीं है, क्योंकि यह चर पर समझौते के आधार पर संतुष्ट है: यदि शर्तें M ₁ , ..., M एक निश्चित गणितीय संदर्भ में होता है, तो यह समझ में आता है। उनमें संबंधित चर चुने जाते हैं ताकि वे मुक्त चर से भिन्न हों।

यदि सेट FV (M) खाली है, तो M को कॉम्बीनेटर कहा जाता है। सभी कॉम्बिनेटरों के सेट को in ₀ से दर्शाया गया है:

≣ ₀ Λ {M Λ ≣ | FV (M) = =}।

निम्नलिखित अनुपात β, β और β कटौती हैं :

(N {((λx.M) एन, एम [एक्स: = एन]) | एम, एन ∈ Λ};
() {(λx.M x, M) | एम M), एक्स V एफवी (एम)};
β β βη β β।

एक अभिव्यक्ति जिसका छेद उपपरिवर्तन को एक संदर्भ कहा जाता है, को C [] द्वारा निरूपित किया जाता है, और C [M] C के संदर्भ में छेद के लिए अभिव्यक्ति M को प्रतिस्थापित करने का परिणाम है।

यदि If एक कमी है, तो अभिव्यक्ति M एक reduction- रेडेक्स है, अगर σN: (M, N) reduction reduction। आप _σ- रूपांतरण "=:" के बारे में भी बात कर सकते हैं:

(एम, एन) ∈ ∈ ⇒ सी [→] → N सी [एन];
एम M ↠ एम;
एम → ⇒ एन ⇒ एम _{σ σ} एन;
एम → M एन ∧ एन → _σ पी ⇒ एम _σ ; पी;
↠P: M ↠ ↠ P ↠ N ↠ M P ⇒ M =: N।

The- सामान्य रूप अभिव्यक्ति है σ अगर M: M → form form। एक्सटेंसिव λ-पथरी में, रेडेक्स द्वारा हमारा अर्थ है red-रेडेक्स, और सामान्य रूप से ,।-सामान्य रूप। यह कहा जाता है कि M का सामान्य रूप N है यदि M Moreover N। इसके अलावा, conversion-रूपांतरण को आमतौर पर "=" द्वारा निरूपित किया जाता है, और यह कोई संयोग नहीं है: औपचारिक रूप से, सिस्टम λβη एक समीकरण सिद्धांत है। चूंकि ऐसे सिद्धांत तर्क से मुक्त हैं, इसलिए उनमें निरंतरता को कुछ अलग तरह से परिभाषित किया गया है।

हम समानता को M = N के सूत्र के रूप में मानते हैं, जहाँ M, N, λ-अभिव्यक्तियाँ हैं; यदि M और N कॉम्बिनेटर हैं तो ऐसी समानता को बंद कर दिया गया है । बता दें कि T एक औपचारिक सिद्धांत है जिसके सूत्र समानताएं हैं। तब वे कहते हैं कि टी सुसंगत है (और वे कोन (टी) लिखते हैं) यदि हर बंद समानता टी में सिद्ध नहीं है। अन्यथा, वे कहते हैं कि टी विरोधाभासी है । Λβη पर विचार करने का एक कारण यह है कि इस सिद्धांत की एक निश्चित पूर्णता संपत्ति है। एक समीकरण सिद्धांत T को हिल्बर्ट-पोस्ट पूर्ण (संक्षिप्त एचपी-पूर्ण) कहा जाता है यदि सिद्धांत की भाषा में किसी भी समानता M = N के लिए T या M = N सिद्ध है या T + (M = N) विरोधाभासी है। एचपी-पूर्ण सिद्धांत प्रथम-क्रम तर्क के लिए मॉडल सिद्धांत में अधिकतम सुसंगत सिद्धांतों के अनुरूप हैं।

एक रणनीति एक मानचित्रण F: Λ → ∀ है कि apping M: M a F (M)। एक-चरणीय रणनीति के लिए, M: M → F (M) धारण करता है। एक रणनीति को सामान्यीकरण कहा जाता है यदि, किसी भी अभिव्यक्ति M के लिए एक सामान्य रूप N है, जिसमें कुछ संख्या n, F ⁿ (M) left N के लिए है। बाएं कमी F _l सबसे सरल एक-चरण सामान्यीकरण रणनीति में से एक है: इसमें β-redex, आइकॉन चुनने का समावेश है। "“ "जिसमें अन्य red-redexes की तुलना में बाईं ओर या η-redexes नहीं हैं, तो बाईं ओर η-redex के समान है। इस प्रकार, यदि दो शब्दों का एक सामान्य सामान्य रूप है, तो बाईं कमी का उपयोग करके, इसी सूत्र के प्रमाण को बहुत सरल चरणों में प्राप्त किया जा सकता है। यदि सूत्र अप्राप्य है, तो या तो प्रक्रिया बिल्कुल भी पूरी नहीं होती है, या यह विभिन्न सामान्य रूपों पर समाप्त होती है।

चीनी

कॉम्बिनेटर का सेट comb सबसे छोटा सेट a ⁺ को अनुप्रयोग द्वारा बंद करने के रूप में उत्पन्न करता है :

Ξ Ξ Ξ ⁺ ;
एम, एन, ∈ ⁺ ⇒ Μ ∈ ∈। ⁺ ।

एक सेट ∈ को आधार कहा जाता है यदि calledM called ∃ ₀ : ∈N called called ⁺ : M = N.

एस और के का उपयोग करके मनमाना अमूर्त मॉडलिंग की जा सकती है:

एस। Λx.λy.λz.xz (yz);
के K λx.λy.x;
मैं ≣ λx.x = SKK;
x .P FV (P) ⇒ λx.P = KP;
λx.PQ = S (λx.P) (λx.Q)।

इसलिए, कॉम्बिनेटर के और एस एक आधार को परिभाषित करते हैं। एम का एक मनमाना कॉम्बिनेटर अक्सर एक λ-अभिव्यक्ति के रूप में नहीं, बल्कि एक्सिओम्स का उपयोग करके वर्णित किया जाता है। उदाहरण के लिए, कॉम्बिनेटरियल लॉजिक सीएल की औपचारिक प्रणाली को दो स्वयंसिद्धों द्वारा परिभाषित किया गया है:

केपीक्यू = पी;
SPQR = PR (QR)।

एकल बिंदु आधार मौजूद हैं: इनमें से एक आधार कोम्बिनेटर द्वारा परिभाषित किया गया है

एक्स ≣ λx.x केएस के।

वास्तव में, यह सत्यापित करना आसान है कि XXX = K और X (XX) = S।

मानक कॉम्बिनेटरों को न केवल कॉम्बिनेटरियल लॉजिक के लिए कुछ आधार बनाने के लिए माना जाता है, बल्कि कई अन्य उपयोगी λ-अभिव्यक्तियाँ भी हैं। पहले उदाहरणों में से एक आमतौर पर एक साधारण कॉम्बिनेटर द्वारा दिया जाता है जिसमें एक सामान्य आकार नहीं होता है:

Ω ω Ω ω, जहां Ω x λx.x एक्स।

इसके अलावा, सत्य मान T and K और F x λx.I को BMN द्वारा "यदि B, तो M, अन्यथा N" ऑपरेशन से निरूपित करना संभव बनाता है। वास्तव में: यदि बी = टी, तो अभिव्यक्ति एम है; यदि बी = एफ, तो अभिव्यक्ति एन है। यदि बी टी और एफ से अलग है, तो परिणाम मनमाना हो सकता है।

सेट सिद्धांत के रूप में, λ-पथरी में एक जोड़ा जोड़े को परिभाषित कर सकते हैं:

[एम, एन] x λx.x MN, [एम, एन] टी N एम, [एम, एन] एफ] एन।

एक डिजिटल सिस्टम कोम्बिनेटर का एक क्रम है system0⎡, ⎤1⎡, is2⎤ ... जिसके लिए एक अनुसरण S ⁺ और शून्य शून्य के लिए एक चेक है :

एस ⁺ ⎤n ⁺ = ⎡n + 1⎤;
शून्य ⎡0ero = टी;
शून्य eron + 1⎤ = F.

एक मानक डिजिटल प्रणाली में चयनित

≣0≣ ⎡ I;
एस ⁺ ] λx। [एफ, एक्स];
शून्य ≣ λx.x टी।

एक डिजिटल प्रणाली को पर्याप्त कहा जाता है यदि सभी पुनरावर्ती कार्य इसके सापेक्ष निश्चित हैं। इस संपत्ति को पूरा करने के लिए, यह पर्याप्त है कि पूर्ववर्ती कार्य P ^{- पाया जाए} । एक मानक डिजिटल प्रणाली के लिए, यह एक संयोजन है

पी ^- λ λx.x एफ।

Λ-पथरी के मुख्य परिणामों में से एक निश्चित बिंदु प्रमेय है: किसी भी एफ के लिए एक्स ऐसा है जैसे कि एफएक्स = एक्स। इसका प्रमाण रचनात्मक है। W X λx.F (xx) और X। W W। तब हमारे पास आवश्यकतानुसार X ≣ (λx.F (xx)) W = F (WW) = FX है। पाठक ने इस प्रमेय के प्रमाण में एक विशेषता देखी होगी। उस एफएक्स = एक्स को स्थापित करने के लिए, हम एक्स शब्द से शुरू करते हैं और इसे एफएक्स पर कम करते हैं, और इसके विपरीत नहीं।

एक निश्चित बिंदु कॉम्बिनेटर एक M शब्द है, जो कि किसी भी F, MF = F (MF) के लिए है, अर्थात, MF, F के लिए एक निश्चित बिंदु है। अक्सर, एक निश्चित बिंदु कॉम्बिनेटर का एक उदाहरण है

Y Y λf। (Λx.f (xx)) (λx.f (xx))।

फिक्स्ड-पॉइंट कॉम्बिनेटर आपको निम्न प्रकार की समस्याओं को हल करने की अनुमति देता है: एफ का निर्माण ऐसे करें

F xy = F yx F

वास्तव में, समाधान सरल है:

F xy = F yx F समानता से अनुसरण करता है F = λx.λy.F yx F,

और यह F = (λf.λx.λy.fyxf) F से आता है।

अब F put Y (λf.λx.λy.fyxf) डालें, और यह सब ठीक है।

टोपोलॉजी

हम कुछ संकेतन पेश करते हैं। सबसे पहले, मैटलैम्बडा एब्स्ट्रक्शन λ x.f (x) सेट-थ्योरैटिक फंक्शन f का नाममात्र संकेतन है, उदाहरण के लिए ( λ x.x ² + 1) (3) = 10. दूसरा, हम परिमित अनुक्रमों के कोड को निर्धारित करते हैं (किसी भी मानक के लिए) प्राकृतिक संख्या के साथ उनकी एन्कोडिंग)

Seq = {<n ₁ , ..., n _k > | k k N, n ₁ , ..., n _k } N} <{<>};
lh (<>) = 0;
α = <n ₁ , ..., n _k > ₁ Seq ⇒ lh (α) = k;
α = <m ₁ , ..., m _p >, <= <n ₁ , ..., n _q > ∈ Seq ⇒ a * b = <m ₁ , ..., m _p , n ₁ , ..., n _q >;
α = <m ₁ , ..., m _p >, <= <n ₁ , ..., n _q > ₁ Seq ∧ p ∧ q ₁ m ₁ = n _{1 1} ... ∧ m _p = n _p ⇒ α _{1 1} ।

D = (D, ⊑) एक आंशिक रूप से आदेश दिया गया है जो प्रतिवर्ती संबंध, के साथ है। इसके बाद सब्मिट X is D को निर्देशित किया जाता है यदि

X X ∈ ∧ ,x, y ∃ X: ∈z: X: x ∧ z। Y ∧ z।

इसके अलावा, डी को पूर्ण कहा जाता है यदि, किसी भी उपसमुच्चय एक्स there डी के लिए, एक वर्चस्व ∈X there डी मौजूद है और एक तल ⊥ है:

:: D: ∈x ∃⊥ D::: x।

पूर्ण रूप से ऑर्डर किए गए सेट (D, is) पर स्कॉट टोपोलॉजी को निम्नानुसार परिभाषित किया गया है: सेट O if D को खुला माना जाता है यदि

1) x) O ⊑ x x y ⇒ y; O;
2) एक्स) डी ⊔ ∈ एक्स ⇒ ओ ⇒ एक्स ≠ ओ ∅ ⊆।

आंशिक नक्शा φ: X is Y एक मानचित्र है जैसे कि DOM (φ) of X की परिभाषा का डोमेन। x, X के लिए, संकेतन φ (x) that का अर्थ है कि φ (x) परिभाषित है, अर्थात x φ DOM (φ) ); ↑ (x) ↑ का अर्थ है कि φ (x) परिभाषित नहीं है, अर्थात, x ↑ DOM (φ)।

यदि symbols प्रतीकों का एक निश्चित समूह है, तो आंशिक रूप से tree-लेबल वाला पेड़ आंशिक मानचित्रण है ↝: Seq N ↝ × N ऐसा

1) ∧ (σ) σ φ ≤ σ φ ⇒ τ (τ) σ;
2) n (σ) = <a, n> ⇒ ≥k: n: φ (σ * <k>) σ।

आंशिक रूप से Σ-लेबल वाले पेड़ underlying में निहित नग्न वृक्ष partial पेड़ ’है

T T = {<>} ∪ {। | * = φ '* * <k> σ σ ()') = <a, n> σ k <n}।

यदि If σ T _φ और φ (=) = <a, n> है, तो नोड a पर एक लेबल कहा जाता है। यदि,,, T, _φ σ (↑) σ के लिए, तो हम कहते हैं कि नोड। बिना लेबल का है। आंशिक रूप से चिह्नित पेड़ों को बड़े अक्षरों में दर्शाया जाएगा और हम ((T _A और A (α) = ⊥ के बजाय (A A लिखेंगे जब A (α) ↑, लेकिन फिर भी α will A।

अगर x = {λx _1. ... λx _n .x | n, 0, x ₁ , ..., x _n , x Λ x}, तो आंशिक रूप से Σ-लेबल वाले पेड़ को बोहम प्रकार का पेड़ कहा जाता है । ऐसे सभी पेड़ों के सेट को बी द्वारा निरूपित किया जाता है। नोड α से शुरू होने वाले A का उप योग A _α = λ α.A (α * β) है। जाहिर है, viousA: B: Aα: A _α ∀ B।

कॉम्बीनेटरियल एम अगर हल है तो

∃n: 1N ₁ , ..., N _n Λ ∃ ₀ : MN ₁ ... N _n = I।

उदाहरण के लिए, फिक्स्ड-पॉइंट कॉम्बिनेटर निर्णायक है, क्योंकि Y (KI) = KI (Y (KI)) = I. दूसरी ओर, Ω v असाध्य है। एक मनमाना λ-अभिव्यक्ति संयुक्ताक्षर λx _{1. है} ... λx _n .M, जहां {x ₁ , ..., x _n } = FV (M)।

Λ-अभिव्यक्ति M एक अग्रणी सामान्य रूप है यदि इसका रूप है

M। Λx _1. ... λx _n .x M ₁ ... M _m , m, n। 0।

ऐसा कहा जाता है कि M का सिर सामान्य रूप N है यदि M = N। किसी अभिव्यक्ति का शीर्ष सामान्य रूप जो पहली बार अपनी बाईं कमी से प्राप्त होता है, मुख्य कहलाता है।

वड्सवर्थ ने λ-अभिव्यक्तियों का एक वर्ग पेश किया जिसका कोई प्रमुख सामान्य रूप नहीं है, और तर्क दिया कि इस वर्ग के तत्वों को λ-पथरी में अर्थहीन अभिव्यक्ति माना जाना चाहिए। उनके पास निम्नलिखित महत्वपूर्ण परिणाम भी हैं: एक λ-अभिव्यक्ति यदि केवल एक सामान्य सामान्य रूप है, तो यह महत्वपूर्ण है। इस प्रकार, एम की अशुद्धता से यह निम्नानुसार है कि किसी भी अभिव्यक्ति के लिए एन ₁ , ..., एन _एन, अभिव्यक्ति एमएन ₁ ... एन _{एन का} सामान्य रूप नहीं है।

बी (एम) द्वारा निरूपित शब्द एम के लिए बोहम पेड़ , निम्नानुसार परिभाषित प्रकार का एक बोहम पेड़ है:

1) यदि M असाध्य है, तो BT: BT (() (↑) uns,
2) यदि M हल करने योग्य है और उसका प्रमुख सामान्य रूप λx _{1 है} ... λx _n .x M ₀ ... M _{m - 1} , उसके बाद

बीटी (एम) (<>) = <λx _1. ... λx _n .x, m>;
k <m ⇒ BT (M) (<k> * =) = BT (M _k ) (σ);
k> m ⇒ BT (M) (<k> * ↑) BT।

स्कॉट टोपोलॉजी के साथ आंशिक रूप से ऑर्डर किए गए सेट बी = (बी, with) पर विचार करें। सेट पर पेड़ की टोपोलॉजी सबसे छोटी टोपोलॉजी है जिसमें मैप बीटी निरंतर है: B. → बी। दूसरे शब्दों में, Λ के खुले उप-अंशों में फॉर्म बीटी ^-1 (ओ) होता है, जहां बी के बाद स्कॉट टोपोलॉजी में ओ खुला है।

पेड़ों की टोपोलॉजी का उपयोग करना, व्यक्ति सामयिक दृष्टि से λ-पथरी से संबंधित सामान्य अवधारणाओं को व्यक्त कर सकता है। उदाहरण के लिए, सामान्य रूप अलग-अलग बिंदुओं के रूप में निकलते हैं, और अघुलनशील अभिव्यक्तियाँ कॉम्पैक्टेशन के बिंदु बनते हैं , अर्थात ऐसे बिंदु जिनका एकमात्र पड़ोस ही स्थलीय स्थान है।

यह साबित हो जाता है कि top पर पेड़ों की टोपोलॉजी में आवेदन और अमूर्तता निरंतर है, और आवेदन के लिए यह दिलचस्प परिणामों के साथ एक nontrivial परिणाम है। उदाहरण के लिए, सॉल्व करने योग्य शब्दों का सेट ⊆ Λ खुला है। वास्तव में, किसी भी पूर्ण रूप से ऑर्डर किए गए सेट में, सेट {x | x x ≠} स्कॉट द्वारा खुला। इसलिए, सेट सोल = बीटी ^-1 {ए | ≠} ⊥ में खुला है।