Vypočítatelná topologie - Computable topology

Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Specifický problém je: Spousta otázek interpunkce a velkých písmen a konvencí WP: MOS a WP: MOSMATH je třeba se podívat. Prosím pomozte vylepšit tento článek jestli můžeš. (prosinec 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Vypočítatelná topologie je obor v matematice, který studuje topologickou a algebraickou strukturu výpočet. Vypočitatelnou topologii nelze zaměňovat s algoritmickou nebo výpočetní topologie, která studuje aplikaci výpočtu na topologii.

Topologie lambda kalkulu

Jak ukazuje Alan Turing a Alonzo Church, λ-kalkul je dostatečně silný, aby popsal všechny mechanicky vypočítatelné funkce (viz Církev – Turingova teze ).^[1][2][3] Lambda-kalkul je tedy efektivně programovací jazyk, ze kterého lze sestavit další jazyky. Z tohoto důvodu při zvažování topologie výpočtu je běžné zaměřit se na topologii λ-kalkulu. Všimněte si, že to nemusí být nutně úplný popis topologie výpočtu, protože funkce, které jsou ekvivalentní ve smyslu Church-Turing, mohou mít stále různé topologie.

The topologie λ-kalkulu je Scottova topologie, a pokud je omezeno na spojité funkce počet volných λ-kalkulů je a topologický prostor spoléhající se na stromová topologie. Jak topologie Scott, tak Tree vykazují kontinuitu s ohledem na binární operátory žádosti (f aplikován na a = fa) a abstrakce ((λx.t (x)) a = t (a)) s modulárním vztahem ekvivalence založeným na shoda. Bylo zjištěno, že λ-algebra popisující algebraickou strukturu lambda-kalkulu je rozšířením kombinatorická algebra, s prvkem zavedeným pro přizpůsobení abstrakci.

Napište zdarma λ-kalkul zachází s funkcemi jako s pravidly a nerozlišuje funkce a objekty, na které jsou aplikovány, což znamená λ-počet typ volný, uvolnit. Vedlejší produkt typu λ-kalkulu typu je efektivní vypočítatelnost ekvivalentní obecná rekurze a Turingovy stroje.^[4] Soubor λ-pojmů lze považovat za funkční topologii, ve které může být funkční prostor vložený, což znamená λ zobrazení v prostoru X jsou taková, že λ: X → X.^[4][5] Představen v listopadu 1969, Dana Scott Teoretický model netypové množiny sestrojil správnou topologii pro jakýkoli model lambda, jehož funkční prostor je omezen na spojité funkce.^[4][5] Výsledek a Scott kontinuální Topologie λ-kalkulu je funkční prostor postavený na sémantice programování, která umožňuje kombinatoriku pevných bodů, například Y kombinátor a datové typy.^[6][7] Do roku 1971 byl λ-kalkul vybaven k definování jakéhokoli sekvenčního výpočtu a mohl být snadno přizpůsoben paralelním výpočtům.^[8] Redukovatelnost všech výpočtů na λ-počet umožňuje, aby si tyto λ-topologické vlastnosti osvojily všechny programovací jazyky.^[4]

Výpočetní algebra z algebry λ-kalkulu

Na základě operátorů uvnitř lambda kalkul, aplikace a abstrakce, je možné vyvinout algebru, jejíž skupinová struktura používá aplikaci a abstrakci jako binární operátory. Aplikace je definována jako operace mezi lambda podmínky produkovat λ-termín, např. aplikace λ na lambda člen A produkuje lambda výraz λa. Abstrakce zahrnuje nedefinované proměnné tím, že jako funkci přiřazující proměnnou označuje λx.t (x) A na lambda výraz s hodnotou t (a) pomocí operace ((λ x.t (x)) a = t (a)). A konečně vztah ekvivalence objeví se, který identifikuje λ-termíny modulo konvertibilní termíny, příkladem je normální forma beta.

Scottova topologie

Scottova topologie je nezbytná pro pochopení topologické struktury výpočtu vyjádřené pomocí λ-kalkulu. Scott zjistil, že po zkonstruování funkčního prostoru pomocí kalkulu λ získá a Kolmogorovův prostor, a ${ displaystyle T_ {o}}$ topologický prostor, který je vystaven bodová konvergence, ve zkratce topologie produktu.^[9] Je to schopnost vlastního homeomorfismu a také schopnost vložit každý prostor do takového prostoru Scott kontinuální, jak bylo dříve popsáno, což umožňuje Scottovu topologii aplikovat na teorii logiky a rekurzivní funkce. Scott přistupuje ke své derivaci pomocí a úplná mříž, což má za následek topologii závislou na struktuře mřížky. Je možné zobecnit Scottovu teorii s použitím kompletní dílčí objednávky. Z tohoto důvodu je obecnější chápání výpočetní topologie poskytováno prostřednictvím úplných dílčích objednávek. Znovu provedeme iteraci, abychom se seznámili s notací, která bude použita během diskuse o Scottově topologii.

Kompletní dílčí objednávky jsou definovány takto:

Nejprve vzhledem k částečně objednaná sada D = (D, ≤), neprázdná podmnožina X ⊆ D je režie pokud ∀ x, y ∈ X ∃ z ∈ X kde X≤ z & y ≤ z.

D je kompletní částečná objednávka (CPO) pokud:

· Každý směrovaný X ⊆D má a supremum, a:

∃ dno prvek ⊥ ∈ D takové, že ∀ X ∈ D ⊥ ≤ X.

Nyní jsme schopni definovat Scottova topologie nad CPO (D, ≤).

Ó ⊆ D je otevřeno li:

1. pro x ∈ O, a x ≤ y, pak y ∈ O, tj. O je horní sada.
2. pro směrovanou množinu X ⊆ D a supremum (X) ∈ O, pak X ∩ O ≠ ∅.

Pomocí Scottovy topologické definice otevřeného je zřejmé, že jsou splněny všechny topologické vlastnosti.

· ∅ a D, tj. Prázdná množina a celý prostor, jsou otevřené.

· Libovolné svazky otevřených množin jsou otevřené:

Důkaz: Předpokládejme ${ displaystyle U_ {i}}$ je otevřený, kde já ∈ I, já jsem indexová sada. Definujeme U = ∪ { ${ displaystyle U_ {i}}$ ; já ∈ já}. Vzít b jako prvek horní množiny U, tedy a ≤ b pro některé A ∈ U Musí to tak být A ∈ ${ displaystyle U_ {i}}$ pro některé i podobně b ∈ rozrušený (${ displaystyle U_ {i}}$). U proto musí být od té doby také horní ${ displaystyle U_ {i}}$ ∈ U.

Podobně, pokud D je směrovaná množina se supremem v U, pak za předpokladu sup (D) ∈ ${ displaystyle U_ {i}}$kde ${ displaystyle U_ {i}}$je otevřeno. Existuje tedy b ∈ D kde b ∈ ${ displaystyle U_ {i} čepice D subseteq U čepice D}$. Spojení otevřených množin ${ displaystyle U_ {i}}$je tedy otevřený.

· Otevřené sady pod křižovatkou jsou otevřené:

Důkaz: Vzhledem k tomu, dvě otevřené sady, U a PROTI, definujeme Ž = U∩PROTI. Li Ž = ∅ tedy Ž je otevřeno. Pokud není prázdné, řekněte b ∈ rozrušení (W) (horní sada W), pak pro některé A ∈ Ž, A ≤ b. Od té doby A ∈ U∩PROTI, a b prvek horní sady obou U a PROTI, pak b ∈ Ž.

Nakonec, pokud D je zaměřená sada se supremem v Ž, pak za předpokladu sup (D) ∈ ${ displaystyle U cap V}$. Takže je A ∈ ${ displaystyle U cap D}$ a b ∈ ${ displaystyle V cap D}$. Od té doby D směřuje tam je C ∈ D s ${ displaystyle a leq c, b leq c}$; a od té doby U a PROTI jsou horní sady, C ∈ ${ displaystyle U cap V}$ také.

I když to zde není zobrazeno, je tomu tak v případě mapy ${ displaystyle f: D rightarrow D ^ {'}}$ je spojitý právě tehdy F(sup (X)) = sup (F(X)) pro všechny řízené X⊆D, kde F(X) = {F(X) | X ∈ X} a druhé supremum v ${ displaystyle D ^ {'}}$.^[4]

Než začneme vysvětlovat, že aplikace jako společný pro λ-kalkul je spojitá v Scottově topologii, vyžadujeme určité porozumění chování supremů nad spojitými funkcemi, jakož i podmínky nezbytné pro součin prostorů, jmenovitě

1. S ${ displaystyle {f_ {i}} _ {i} subseteq [D rightarrow D ^ {'}]}}$ být řízenou rodinou map ${ displaystyle f (x) = pohár _ {i} f_ {i} (x)}$ pokud jsou dobře definované a spojité.
2. Pokud F ${ displaystyle subseteq [D rightarrow D ^ {'}]}$ je směrován a CPO a ${ displaystyle [D rightarrow D ^ {'}]}$ cpo kde sup ({F(X) | F ∈ F}).

Nyní ukážeme kontinuitu aplikace. Pomocí následující definice aplikace:

Ap: ${ displaystyle [D rightarrow D ^ {'}] krát D rightarrow D ^ {'}}$ kde Ap(F,X) = F(X).

Ap je kontinuální s ohledem na Scottovu topologii na produktu (${ displaystyle [D rightarrow D ^ {'}] krát D rightarrow D ^ {'}}$) :

Důkaz: λx.f (x) = f je spojité. Nechť h = λ f.f (x). Pro režii F${ displaystyle subseteq [D rightarrow D ^ {'}]}$

h(sup (F)) = sup (F)(X)

= sup ({F(X) | F ∈ F} )

= sup ({h(F) | F ∈ F} )

= sup ( h(F) )

Podle definice Scottovy kontinuity h bylo zobrazeno nepřetržitě. Vše, co je nyní nutné prokázat, je to aplikace je spojitý, když jsou samostatné argumenty spojité, tj. ${ displaystyle [D rightarrow D ^ {'}]}$a ${ displaystyle D rightarrow D ^ {'}}$jsou v našem případě spojité F a h.

Nyní abstrahujeme, abychom ukázali náš argument ${ displaystyle f: D krát D ^ {'} rightarrow D ^ {' '}}$ s ${ displaystyle g = lambda x.f (x, x_ {0})}$ a ${ displaystyle d = lambda x ^ {'}. f (x_ {0}, x ^ {'})}$ jako argumenty pro D a ${ displaystyle D ^ {'}}$ respektive pak pro směrovaný X ⊆ D

${ displaystyle g ( sup (X)) = f ( sup (X), x_ {0} ^ {'}))}$

= f (sup ((x,${ displaystyle x_ {0} ^ {'}}$) | x ∈ X}))

(od té doby F je spojitý a {(x,${ displaystyle x_ {0} ^ {'}}$) | x ∈ X}) směřuje):

= sup ({f (x,${ displaystyle x_ {0} ^ {'}}$) | x ∈ X})

= sup (g (X))

g je tedy spojité. Stejným postupem lze ukázat, že d je spojité.

Nyní se ukázalo, že aplikace je podle Scottovy topologie spojitá.

Abychom prokázali, že Scottova topologie je vhodná pro λ-kalkul, je nutné prokázat abstrakce zůstává spojitá nad Scottovou topologií. Po dokončení bude prokázáno, že matematický základ λ-kalkulu je dobře definovaným a vhodným kandidátským funkčním paradigmatem pro Scottovu topologii.

S ${ displaystyle f v [D krát D ^ {'} pravá šipka D ^ {' '}]}}$ definujeme ${ displaystyle { check {f}}}$ (x) = λ y ∈ ${ displaystyle D ^ {'}}$f (x, y) Ukážeme:

(i) ${ displaystyle { check {f}}}$ je spojitý, což znamená ${ displaystyle { check {f}}}$ ∈ ${ displaystyle [D rightarrow [D ^ {'} rightarrow D ^ {' '}]}}$

ii) λ ${ displaystyle f. { check {f}}: [D krát D ^ {'} rightarrow D ^ {' '}] rightarrow [D rightarrow [D ^ {'} rightarrow D ^ {'' }]}$ je spojitý.

Důkaz (i): Nechť je tedy směrováno X ⊆ D

${ displaystyle { check {f}}}$(sup (X)) = λ y.f (sup (X), y)

= λ y.${ displaystyle sup _ {x v X}}$(f (x, y))

= ${ displaystyle sup _ {x v X}}$(λy.f (x, y))

= sup (${ displaystyle { check {f}}}$(X))

Důkaz (ii): Definování L = λ ${ displaystyle f. { zaškrtněte {f}}}$ pak pro F ${ displaystyle subseteq [D krát D ^ {'} pravá šipka D ^ {' '}]}}$ režie

L (sup (F)) = λ x λ y. (sup (F)) (x, y))

= λ x λ y. ${ displaystyle sup _ {y ve F}}$f (x, y)

= ${ displaystyle sup _ {y ve F}}$λx λy.f (x, y)

= sup (L (F))

Nebylo prokázáno, jak a proč λ-počet definuje Scottovu topologii.

Böhmovy stromy a výpočetní topologie

Böhmovy stromy, snadno graficky znázorněné, vyjadřují výpočetní chování a lambda termín. Je možné předvídat funkčnost daného výrazu lambda z odkazu na jeho korelační Böhmův strom.^[4] Stromy Böhm lze vidět poněkud analogicky ${ displaystyle mathbb {R}}$ kde Böhmův strom dané množiny je podobný pokračujícímu zlomku reálného čísla, a co víc, Böhmův strom odpovídající sekvenci v normální forma je konečný, podobný racionální podmnožině Realů.

Böhmovy stromy jsou definovány mapováním prvků v posloupnosti čísel s uspořádáním (≤, lh) a binárním operátorem * na sadu symbolů. Böhmův strom je potom relací mezi sadou symbolů prostřednictvím částečného mapování ψ.

Neformálně lze Böhmovy stromy konceptualizovat takto:

Dáno: Σ = ${ displaystyle perp cup}$ {λ x_ {1} ${ displaystyle cdots}$x_ {n}. y | n ∈ ${ displaystyle mathbb {N}, x_ {1} ... x_ {n}}$y jsou proměnné a označují BT (M) jako Böhmův strom pro lambda výraz M, který máme:

BT (M) = ⊥ pokud M je neřešitelný (tedy jeden uzel)

Více formálně:

Σ je definována jako sada symbolů. Böhmův strom λ termínu M, označený BT (M), je Σ označený strom definovaný takto:

Li M je neřešitelný:

${ displaystyle BT (M) ( langle rangle) = perp,}$

BT (M) (${ displaystyle langle k rangle * alpha}$) je neřešitelný ${ displaystyle forall k, alpha}$

Pokud je M řešitelné, kde M = λ x_ {1}${ displaystyle cdots x_ {n} .yM_ {0} cdots M_ {m-1}}$:

BT (M) (<>) = λ x_ {1} ${ displaystyle cdots x_ {n} .y}$

BT (M) (${ displaystyle langle k rangle * alpha}$) = BT (M_k) (${ displaystyle alpha}$) ${ displaystyle forall alpha}$ a k

= nedefinováno ${ displaystyle forall alpha}$ a k ≥ m

Nyní můžeme přejít a ukázat, že Böhmovy stromy fungují jako vhodné mapování od topologie stromů po topologii Scotta. Umožní člověku vidět výpočetní konstrukce, ať už v rámci Scottovy nebo stromové topologie, jako Böhmovy stromové formace.

Böhmův strom a topologie stromů

Je zjištěno, že Böhmův strom je povoleno pro průběžné mapování od stromové topologie po topologii Scottovou. Konkrétněji:

Začínáme s cpo B = (B, ⊆) na Scottově topologii, s uspořádáním Böhmova stromu označeného M⊆ N, což znamená, že M, N jsou stromy a M výsledky z N. stromová topologie na množině Ɣ je nejmenší množina umožňující souvislou mapu

BT:${ displaystyle Gamma rightarrow}$B.

Ekvivalentní definicí by bylo říci, že otevřené množiny Ɣ jsou obrazem inverzního Böhmova stromu ${ displaystyle BT ^ {- 1}}$ (O) kde O je Scott otevřen B.

Použitelnost stromů Bömh a topologie stromů má mnoho zajímavých důsledků pro termíny λ vyjádřené topologicky:

Normální formy existují jako izolované body.

Neřešitelné termíny λ jsou body zhutnění.

Aplikace a abstrakce, podobné Scottově topologii, jsou na stromové topologii spojité.

Algebraická struktura výpočtu

Nové metody interpretace λ-kalkulu jsou nejen samy o sobě zajímavé, ale umožňují nové způsoby myšlení týkající se chování počítačové vědy. Binární operátor v rámci λ-algebry A je aplikace. Aplikace je označena · a říká se, že dává strukturu ${ displaystyle A = (X, cdot)}$. A kombinatorická algebra umožňuje operátorovi aplikace a funguje jako užitečný výchozí bod, ale zůstává nedostatečný pro kalkulus λ, protože není schopen vyjádřit abstrakci. Algebra λ se stává kombinační algebrou M kombinovanou se syntaktickým operátorem λ *, který transformuje člen B (x, y), s konstantami v M, do C (${ displaystyle { hat {y}}}$) ≡ λ * x.B (x,${ displaystyle { hat {y}}}$). Je také možné definovat rozšíření model obejít potřebu operátoru λ * povolením ∀x (fx = gx) ⇒ f = g. Konstrukce λ-algebry zavedením operátoru abstrakce probíhá následovně:

Musíme zkonstruovat algebru, která umožňuje řešení rovnic jako axy = xyy tak, že a = λ xy.xyy existuje kombinatorická algebra. Relevantní atributy kombinační algebry jsou:

V kombinatorické algebře existuje aplikační struktury. Aplikační struktura W je kombinatorická algebra za předpokladu, že:

· W je non-trival, což znamená W má mohutnost > 1

· W vykazuje kombinatorickou úplnost (viz úplnost základny S-K ). Přesněji řečeno: pro každý člen A ∈ množina členů W a ${ displaystyle x_ {1}, ..., x_ {n}}$ s volnými proměnnými A uvnitř ${ displaystyle {x_ {1}, ..., x_ {n}}}$ pak:

${ displaystyle existuje f pro všechny x_ {1} cdot cdot cdot x_ {n}}$ kde ${ displaystyle fx_ {1} cdot cdot cdot x_ {n} = A}$

Kombinatorická algebra je:

• Nikdy komutativní
• Není asociativní.
• Nikdy konečné.
• Nikdy rekurzivní.

Kombinované algebry zůstávají neschopné působit jako algebraická struktura pro λ-kalkul, přičemž hlavní nevýhodou je absence rekurze. Existence použitelného výrazu ${ displaystyle A (x, { vec {y}}}$) poskytuje dobrý výchozí bod pro vytvoření algebry λ-kalkulu. Je třeba zavést a lambda termín, tj. zahrnout λx.A (x, ${ displaystyle { vec {y}}}$).

Začneme využitím skutečnosti, že v kombinační algebře M, s A (x, ${ displaystyle { vec {y}}}$) v rámci sady podmínek, pak:

${ displaystyle forall { vec {y}}}$ ${ displaystyle existuje b}$ Svatý. bx = A (x, ${ displaystyle { vec {y}}}$).

Potom požadujeme, abychom měli závislost na ${ displaystyle { vec {y}}}$ což má za následek:

${ displaystyle forall x}$ B (${ displaystyle { vec {y}}}$) x = A (x, ${ displaystyle { vec {y}}}$).

B (${ displaystyle { vec {y}}}$) se stává ekvivalentem k λ členu, a proto je vhodně definován takto: B (${ displaystyle { vec {y}}) equiv}$ λ *.

A pre-λ-algebra Nyní lze definovat (pλA).

pλA je aplikační struktura W = (X, ·) taková, že pro každý člen A v množině členů v W a pro každé x existuje člen λ * xA ∈ T (W) (T (W) ≡ členy W) kde (množina volných proměnných λ * xA) = (množina volných proměnných A) - {x}. W musí také prokázat:

${ displaystyle ( beta)}$ (λ * x.A) x = A

${ displaystyle alpha _ {1}}$λ * x.A≡ λ * x.A [x: = y] za předpokladu, že y není volná proměnná A

${ displaystyle alpha _ {2}}$(λ * x.A) [y: = z] ≡λ * x.A [x: = y] za předpokladu, že y, z ≠ xaz nejsou volnou proměnnou A

Před definováním úplné λ-algebry musíme zavést následující definici množiny λ-termínů ve W označených ${ displaystyle Gamma (W)}$ s následujícími požadavky:

a ∈ Ž ${ displaystyle Rightarrow c_ {a} in Gamma (W)}$

x ∈ ${ displaystyle Gamma (W)}$ pro x ∈ (${ displaystyle v_ {0}, v_ {1}, ...}$)

M, N ∈ ${ displaystyle Gamma (W) Rightarrow}$ (MN) ∈ ${ displaystyle Gamma (W)}$

M ∈ ${ displaystyle Gamma (W) Rightarrow}$ (λx.M) ∈ ${ displaystyle Gamma (W)}$

Mapování z výrazů uvnitř ${ displaystyle Gamma (W)}$ ke všem výrazům λ v rámci W, označené * : ${ displaystyle gama (W) pravá šipka mathrm {T} (W)}$, pak lze navrhnout následovně:

${ displaystyle v_ {i} ^ {*} = w_ {i}, c_ {a} ^ {*} = c_ {a}}$

(MN) * = M * N *

(λx.M) * = λ * x * .M *

Nyní definujeme λ(M) k označení rozšíření po vyhodnocení podmínek uvnitř ${ displaystyle Gamma (W)}$.

λx. (λy.yx)${ displaystyle c_ {a}}$ = λx.${ displaystyle c_ {a}}$x v λ(W).

Nakonec získáme celý λ-algebra prostřednictvím následující definice:

(1) λ-algebra je pλA W taková, že pro M, N ∈ Ɣ (W):

λ(Ž) ⊢ M = N ⇒ W ⊨ M = N.

Ačkoli byl namáhavý, byl položen základ pro správný algebraický rámec, pro který lze λ-kalkul, a tedy výpočet, zkoumat v skupinový teoretik způsob.

Reference