Сборка (реализуемость) ⇐ Васина Википедия

[wiki_en]

В теоретической информатике и математической логике «сборки» могут быть неофициально описаны как наборы, оснащенные представлениями для элементов. Реализуемость Топозии являются завершением категорий сборки.

== Мотивация ==

Алгоритмы напрямую не манипулируют объектами, такими как графики или списки, а представления этих объектов. Там может быть несколько типов представлений. Например, графики могут быть представлены с помощью списков смежности или матрицы смежности | соседних матриц. Кроме того, заданный объект может иметь несколько эквивалентных представлений, например, график может быть представлен с любым порядком вершин, а алгоритмы графика должны дать эквивалентные результаты, независимо от того, каким бы ни был порядок вершин при входе. Основная идея, стоящая за сборками, состоит в том, чтобы рассмотреть наборы (такие как набор конечных графиков), где каждый элемент имеет ряд «реализаторов», которые понимаются как его алгоритмические представления. Морфизм между собраниями - это функция между их базовыми наборами, которые могут быть «алгоритмически реализованы», в том смысле, что с учетом представления элемента домена можно вычислить представление его изображения. Например, реализована функция, которая отображает график с MultiSet из его подключенных компонентов: существует алгоритм, который, учитывая представление графика, вычисляет представление мультисета его подключенных компонентов.

В контексте реализуемости полезно не ограничивать определение алгоритмами в тезисе церкви-Тьюринга | Черт-коричневый смысл. Вместо этого сборки определяются по определенной частичной комбинаторной алгебре, которая абстрагирует модель вычислений. Например, первая алгебра Kleene может быть использована для вычислительности церкви.

Возможно, удивительный аспект определения заключается в том, что элементы могут делиться реализаторами. Хотя необычный алгоритмический, это важно для логической стороны реализуемости.

== Определение ==

Пусть < /math> быть фиксированной частичной комбинаторной алгеброй.

Ассамблея '' '' '' s (over a ) - это просто набор | S | , читать «Реализует» между и | s | , так что каждый элемент | s | имеет реализатор, т.е. для всех s \ in | s | , существует a \ in с a \ vdash_s s .

Ассамблея s , как говорят, является '' 'скромным' '' ', когда элементы не делятся реализаторами, то есть для всех s, s' in s, a \ in , если a \ vdash_s s и a \ vdash_s s ' then s = s' . Категория скромных сборок над a обозначена \ operatorname {mod} (a) и является полной подкатегорией \ operatorname {asm} (a) .

* *
Конструктивизм (математика)



Подробнее: https://en.wikipedia.org/wiki/Assembly_(realizability)