6.1: Повсюдне поширення мережевих мов

Last updated
Save as PDF

Page ID: 66323

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Електричні ланцюги, хімічні реакційні мережі, кінцеві автомати, марковські процеси: це все моделі фізичних або обчислювальних систем, які зазвичай описуються за допомогою мережевих діаграм. Ось, наприклад, ми малюємо схему, яка моделює триггера, електричну схему, важливу в пам'яті комп'ютера, яка може зберігати трохи інформації:

$Знімок екрана 2021-01-21 о 1.34.11 PM.png$

Мережеві схеми мають перевірену часом утиліту. У цьому розділі ми зацікавлені в розумінні загальної математичної структури, яку вони поділяють, з метою їх перекладу та уніфікації; наприклад, певні типи марковських процесів можуть бути змодельовані і, отже, вирішені за допомогою схем резисторів. Коли ми розуміємо базові структури, які поділяються мовами мережевих діаграм, ми можемо легко проводити порівняння між відповідними математичними моделями.

На перший погляд схеми мережі виглядають зовсім не так, як схеми підключення, які ми бачили досі. Наприклад, дроти є неспрямованими у наведеному вище випадку, тоді як у категорії, що включає моноїдальні категорії, що спостерігаються в теоріях ресурсів або спільному проектуванні, кожен морфізм має область та кодомен, надаючи йому відчуття напрямку. Тим не менш, ми побачимо, як використовувати категоричні конструкції, такі як універсальні властивості, для створення категоріальних моделей, які точно фіксують вищевказаний тип «мережевої» композиційності, тобто дозволяють ефективно скидати спрямованість, коли це зручно.

Зокрема, ми повернемося до ідеї colimit, яку ми накидали для вас в кінці глави 3, і покажемо, як використовувати коліміти в категорії множин для формалізації ідей зв'язку. Ось ключова ідея.

Підключення через коліміти. Скажімо, ми хочемо встановити деякі вогні: ми хочемо створити схему, щоб, коли ми натискаємо вимикач, світло включається або вимикається. Для початку у нас є купа компонентів схеми: джерело живлення, вимикач, і лампа, підключена до резистора:

$Знімок екрана 2021-01-21 о 1.35.35 PM.png$

Ми хочемо з'єднати їх разом, але є багато способів зробити це. Як слід описати конкретний спосіб, який буде формувати вимикач світла?

По-перше, ми стверджуємо, що схеми дійсно слід розглядати як відкриті ланцюги: кожен несе додаткову структуру «інтерфейсу», що піддає його решті електричного світу. Тут під інтерфейсом ми маємо на увазі певний набір місць або портів, на яких ми можемо з'єднати їх з іншими компонентами.1 Як це так часто зустрічається в теорії категорій, ми починаємо з того, що цей більш-менш очевидний факт явним. Зобразимо доступні порти за допомогою жирного шрифту •. Якщо ми скажемо, що на кожному з трьох малюнків вище порти - це просто звисаючі кінцеві точки проводів, вони будуть перемальовані наступним чином:

$Знімок екрана 2021-01-21 в 1.36.01 PM.png$

Далі ми повинні описати, які порти слід підключати. Ми зробимо це шляхом малювання порожніх кіл ◦ з'єднаних стрілками до двох портів •. Кожен буде свідком зв'язку, кажучи «з'єднайте цих двох!»

$Знімок екрана 2021-01-21 о 1.36.31 PM.png$

Дивлячись на цю картинку, зрозуміло, що нам потрібно зробити: просто визначити - тобто об'єднати або зробити рівними - порти, як зазначено, щоб отримати наступну схему:

$Знімок екрана 2021-01-21 в 1.42.20 PM.png$

Але математика не має зорової кори, за допомогою якої можна генерувати інтуїцію, на яку ми можемо розраховувати з людським читачем, таким як ви. $^{2}$Таким чином, нам потрібно формально вказати, що означає «ідентифікація портів як вказаних» математично. Як з'ясовується, ми можемо зробити це за допомогою скінченних колімітів у заданій категорії C.

Коліміти - це діаграми з певними універсальними властивостями, що є своєрідним епіфним іменем категорії С. Наша мета полягає в тому, щоб отримати коліміти C більш безпосередньо, як своєрідну операцію в певному контексті, так що ми можемо думати про них як про те, що говорять нам, як з'єднати деталі ланцюга разом. З цією метою ми виробляємо певну моноїдальну категорію, а саме категорію коспанів у С, позначену Коспан,$_{C}$ який може зручно упаковувати коліміти С з точки зору власних основних операцій: складу та моноїдального продукту.

Підсумовуючи, перша частина цього розділу присвячена слогану «взаємозв'язок моделі колімітів». Крім універсальних конструкцій, таких як коліміти, однак, ще одним способом опису взаємозв'язку є використання електричних схем. Ми йдемо повним колом, коли виявляємо, що ці схеми підключення сильно пов'язані з коспанами, а значить, і колімітами.

Але математика не має зорової кори, за допомогою якої можна генерувати інтуїцію, на яку ми можемо розраховувати з людським читачем, таким як вас.2 Таким чином, нам потрібно формально вказати, що означає «ідентифікація портів як вказаних» математично. Як з'ясовується, ми можемо зробити це за допомогою скінченних колімітів у заданій категорії C.

Склад операцій і монтажних схем. У цій книзі ми побачили корисність визначення синтаксичних або алгебраїчних структур, які описують роду операції композиції, які мають сенс і можуть бути виконані в даній області застосування. Приклади включають моноїдальні попередні замовлення з відкиданням, реквізит та компактні закриті категорії. Кожен з них має пов'язаний стиль схеми підключення, так що будь-який діаграм проводки цього стилю являє собою операцію композиції, яка має сенс у даній області: перший має сенс у виробництві, другий у потоці сигналу, і третій у спільному проектуванні. Отже, наша друга мета - відповісти на питання: «як ми опишемо композиційну структуру схем підключення в стилі мережі?»

Взаємозв'язок типу мережі можна описати за допомогою чогось, званого категорією гіпер- графа. Грубо кажучи, це категорії, схеми електропроводки яких відносяться до симетричних моноїдальних категорій разом з, для кожної пари натуральних чисел (m, n), значком s$_{m,n}$: m → n. Ці значки, відомі як павуки,$^{3}$ малюються наступним чином:

$Знімок екрана 2021-01-21 о 1.51.56 PM.png$

Два павука можуть розділити ногу, і коли вони це зроблять, ми можемо об'єднати їх в одного павука. Інтуїція полягає в тому, що павуки є точками з'єднання для ряду проводів, і коли дві точки з'єднання з'єднані, вони зливаються, утворюючи ще більше точки з'єднання «connect-y». Ось приклад:

$Знімок екрана 2021-01-21 в 1.52.37 PM.png$

Категорія гіперграфа може мати багато видів павуків з правилом, що павуки різних видів не можуть ділити ногу і, отже, не зливатися, але два павуки одного виду можуть ділити ноги і зливатися. Ми додаємо діаграми павуків до іконографії категорій гіперграфа.

Як ми побачимо, ідеї опису мережевого взаємозв'язку за допомогою категорій колімітів та гіперграфів об'єднуються в понятті теорії. Ми вперше представили ідею теорії в розділі 5.4.2, але тут досліджуємо її більш детально, починаючи з думки про те, що, приблизно кажучи, коспани в категорії FinSet утворюють теорію категорій гіперграфа.

Ми можемо зібрати всі коспани в FinSet в щось, що називається «опера». Через цю книгу ми говорили про використання вільних структур та презентацій для створення екземплярів алгебраїчних структур, таких як попередні замовлення, категорії та реквізити, пристосовані до потреб конкретної ситуації. Операди можуть використовуватися для адаптації самих алгебраїчних структур до потреб конкретної ситуації. Ми обговоримо, як це працює, зокрема, як опери кодують різного роду мови монтажних схем та відповідні алгебраїчні структури, в кінці глави.