De Bruijnův index - De Bruijn index

v matematická logika, de Bruijn index je nástroj, který vynalezl holandský matematik Nicolaas Govert de Bruijn za reprezentaci podmínek lambda kalkul bez pojmenování vázaných proměnných.^[1] Výrazy psané pomocí těchto indexů jsou vůči invariantní α-konverze, takže šek na α-ekvivalence je stejný jako u syntaktické rovnosti. Každý de Bruijnův index je a přirozené číslo který představuje výskyt a proměnná v λ-termínu a označuje počet pojiva které jsou v rozsah mezi tímto výskytem a jeho odpovídajícím pořadačem. Následuje několik příkladů:

• Termín λX. λy. X, někdy nazývané K kombinátor, je zapsáno jako λ λ 2 s De Bruijnovými indexy. Pojivo pro výskyt X je druhým λ v rozsahu.
• Termín λX. λy. λz. X z (y z) (dále jen S kombinátor ), s de Bruijnovými indexy, je λ λ λ 3 1 (2 1).
• Termín λz. (λy. y (λX. X)) (λX. z X) je λ (λ 1 (λ 1)) (λ 2 1). Viz následující obrázek, kde jsou pořadače barevné a odkazy jsou zobrazeny šipkami.

De Bruijnovy indexy se běžně používají v vyšší řád uvažovací systémy jako např automatizované věty provers a logické programování systémy.^[2]

Formální definice

Formálně, λ-podmínky (M, N, ...) zapsané pomocí indexů De Bruijn mají následující syntaxi (závorky jsou povoleny volně):

M, N, ... ::= n | M N | λ M

kde n—přirozená čísla větší než 0 - jsou proměnné. Proměnná n je vázaný pokud je v rozsahu alespoň n pojiva (λ); jinak je volný, uvolnit. Vazebné místo pro proměnnou n je nth pořadač je v rozsah z, počínaje nejvnitřnějším pojivem.

Nejprimitivnější operací na λ-termínech je substituce: nahrazení volných proměnných v termínu jinými termíny. V β-redukce (λ M) Nnapříklad musíme:

1. najděte instance proměnných n₁, n₂, ..., n_k v M které jsou vázány λ v λ M,
2. snížit volné proměnné M aby odpovídalo odstranění vnějšího λ-pojiva a
3. nahradit n₁, n₂, ..., n_k s N, vhodně zvyšující volné proměnné vyskytující se v N pokaždé, aby odpovídal počtu λ-pojiv, pod kterými se příslušná proměnná vyskytuje, když N náhražky jednoho z n_i.

Pro ilustraci zvažte aplikaci

(λ λ 4 2 (λ 1 3)) (λ 5 1)

což by mohlo odpovídat následujícímu termínu psanému obvyklou notací

(λX. λy. z X (λu. u X)) (λX. w X).

Po kroku 1 získáme výraz λ 4 □ (λ 1 □), kde jsou proměnné, které jsou určeny pro substituci, nahrazeny rámečky. Krok 2 dekrementuje volné proměnné a dává λ 3 □ (λ 1 □). Nakonec v kroku 3 nahradíme pole argumentem, konkrétně λ 5 1; první pole je pod jedním pořadačem, takže ho nahradíme λ 6 1 (což je λ 5 1 s volnými proměnnými zvýšenými o 1); druhá je pod dvěma pojivy, takže ji nahradíme λ 7 1. Konečný výsledek je λ 3 (λ 6 1) (λ 1 (λ 7 1)).

Formálně je substituce neomezeným seznamem nahrazení termínů pro volné proměnné, písemné M₁.M₂..., kde M_i je náhradou za ita volná proměnná. Rostoucí operace v kroku 3 se někdy nazývá posun a napsáno ↑^k kde k je přirozené číslo udávající částku ke zvýšení proměnných; například ↑⁰ je substituce identity a ponechává termín beze změny.

Uplatnění náhrady s na termín M je psáno M[s]. Složení dvou substitucí s₁ a s₂ je psáno s₁ s₂ a definováno

M [s₁ s₂] = (M [s₁]) [s₂].

Pravidla pro aplikaci jsou následující:

${ displaystyle { begin {zarovnáno} n [N_ {1} ldots N_ {n} ldots] = & N_ {n} (M_ {1} ; M_ {2}) [s] = & (M_ {1} [s]) (M_ {2} [s]) ( lambda ; M) [s] = & lambda ; (M [1,1 [s ']. 2 [s']. 3 [s '] ldots]) & { text {where}} s' = s uparrow ^ {1} end {zarovnáno}}}$

Kroky uvedené výše pro β-redukci jsou tedy výstižněji vyjádřeny jako:

(λ M) N →_β M [N.1.2.3...].

Alternativy k indexům De Bruijn

Při použití standardní „pojmenované“ reprezentace λ-pojmů, kde se s proměnnými zachází jako se štítky nebo řetězci, je při definování jakékoli operace s pojmy nutné explicitně zpracovat α-převod. Standardní Variabilní konvence^[3] z Barendregt je jeden takový přístup, kde se α-konverze podle potřeby používá k zajištění toho, že:

1. vázané proměnné se liší od volných proměnných a
2. všechny pořadače vážou proměnné, které ještě nejsou v oboru.

V praxi je to těžkopádné, neefektivní a často náchylné k chybám. Vedlo to proto k hledání různých reprezentací takových výrazů. Na druhou stranu je pojmenovaná reprezentace λ-termínů všudypřítomnější a ostatní ji mohou okamžitě pochopit, protože proměnným lze dát popisná jména. I když tedy systém interně používá indexy De Bruijn, zobrazí se uživatelské rozhraní se jmény.

De Bruijnovy indexy nejsou jediným vyjádřením λ-pojmů, které zabraňují problému α-konverze. Mezi pojmenovanými reprezentacemi je nominální techniky Pitts and Gabbay je jeden přístup, kde se reprezentace λ-termínu považuje za třídu ekvivalence všech termínů přepisovatelný k tomu pomocí proměnných permutací.^[4] Tento přístup využívá balíček nominálních datových typů Isabelle / HOL.^[5]

Další běžnou alternativou je odvolání k reprezentace vyššího řádu kde λ-pojivo je považováno za skutečnou funkci. V takových reprezentacích jsou problémy α-ekvivalence, substituce atd. Identifikovány se stejnými operacemi v a meta-logika.

Při uvažování o meta-teoretických vlastnostech deduktivního systému v a důkaz asistent, je někdy žádoucí omezit se na reprezentace prvního řádu a mít schopnost pojmenovat nebo přejmenovat předpoklady. The lokálně bezejmenný přístup používá smíšené zastoupení proměnných - De Bruijnovy indexy pro vázané proměnné a názvy volných proměnných -, která je v případě potřeby schopna těžit z α-kanonické formy de Bruijnových indexovaných výrazů.^[6][7]

Viz také

• The De Bruijnova notace pro λ-termíny.
• Kombinovaná logika, což je podstatnější způsob, jak eliminovat názvy proměnných.

Reference