Отказ от ответственности: я очень мало знаю о теории сложности.
Извините, но на самом деле нет способа задать этот вопрос, не будучи (ужасно) лаконичным:
Какими должны быть морфизмы в «категории» машин Тьюринга?
Это, очевидно, субъективно и зависит от толкования теории, поэтому в идеале ответ на этот вопрос должен дать некоторые доказательства и аргументацию в поддержку ответа.
Я хотел бы подчеркнуть, что я ищу категорию машин Тьюринга, а не формальных языков, например. В частности, я думаю, что мои морфизмы должны содержать более точную информацию, чем сокращения или что-то подобное (хотя я не уверен).
Конечно, если в литературе уже есть хорошо известная и используемая категория, я бы хотел знать, что это такое.
cc.complexity-theory
turing-machines
ct.category-theory
Саал Хардали
источник
источник
Ответы:
Саал Хардали отметил, что он хотел, чтобы категория машин Тьюринга занималась геометрией (или, по крайней мере, теорией гомотопии). Тем не менее, есть много разных способов достижения похожих целей.
Существует очень сильная аналогия между вычислимостью и топологией. Интуиция заключается в том, что завершение / нетерминация подобны пространству Серпинского, поскольку окончание является конечно наблюдаемым (то есть открытым), а нетерминация - нет (не открытым). См. Примечания к лекции Мартина Эскардо. Синтетическая топология типов данных и классических пространств для умеренно нежного, но всестороннего введения в эти идеи.
В параллельных и распределенных вычислениях часто полезно думать о возможных выполнениях программы как о пространстве, и тогда различные ограничения синхронизации могут быть выражены как гомотопические свойства пространства. (Тот факт, что исполнение имеет временной порядок, по-видимому, требует направленной теории гомотопий, а не обычной теории гомотопий.)
См. Статью Эрика Губо « Некоторые геометрические перспективы теории параллелизма» для более подробной информации. Также см. Статью Мориса Херлихи и Нира Шавита, удостоенную премии Гёделя, «Топологическая структура асинхронной вычислимости» , в которой решены некоторые давние открытые проблемы в теории распределенного программирования.
Третья идея приходит через теорию гомотопического типа, благодаря открытию, что теория типа Мартина-Лёфа является (вероятно?) Синтаксическим представлением (в смысле образующих и отношений) теории омега-группоидов - то есть моделей абстрактного гомотопическая теория. Лучшее введение в эти идеи - книга по теории гомотопических типов .
Обратите внимание, что все эти идеи сильно отличаются друг от друга, но все еще используют геометрические интуиции! И есть еще другие, которые я не знаю, такие как использование, возникающее в геометрической теории сложности, и способ, которым теории цепей могут быть описаны в терминах (со) гомологии теории графов .
По сути, когда вы делаете CS, геометрия является инструментом - вы используете его для формализации своей интуиции, чтобы вы могли получить рычаги за счет огромного объема работы, которая была проделана над ней. Но это усилитель идеи, а не замена идеи!
источник
Если ваши объекты являются машинами Тьюринга, есть несколько разумных возможностей для морфизмов. Например:
1) Рассматривайте машины Тьюринга как автоматы, которыми они являются, и рассматривайте обычные морфизмы автоматов (карты между алфавитами и состояниями, которые согласуются друг с другом), которые также либо сохраняют движения головки (голов) ленты, либо точно обратные их (например, всякий раз, когда исходная ТМ идет налево, целевая ТМ идет направо и наоборот).
2a) Рассмотрите симуляции или бисимуляции .
3) Рассмотрим граф переходов машины Тьюринга (каждая вершина представляет собой полное описание состояния машины и лент с направленными ребрами, соответствующими переходам, которые должна выполнять ТМ), и рассмотрим морфизмы графов. Однако для ТМ это очень грубое отношение, поскольку оно по существу игнорирует локальную природу вычислений (например, игнорируется, каково содержимое лент).
Я думаю, что настоящий вопрос заключается в следующем: что вы хотите знать о ТМ или делать с ними? В отсутствие этого трудно приводить аргументы для какого-либо одного определения над другим, за пределами естественности (в обычном смысле этого слова, а не в категориальном смысле).
источник
Вас могут заинтересовать категории Тьюринга Робина Кокетта и Питера Хофстра. С точки зрения теории категорий на вопрос «что категория машин Тьюринга» менее интересен , чем «что категорический структура , которая лежит в основе вычислений». Таким образом, Робин и Питер идентифицируют общий вид категории, которая подходит для разработки теории вычислимости. Тогда есть несколько возможностей для определения такой категории, начиная с машин Тьюринга. Зачем иметь одну категорию, если вы можете иметь целую категорию из них?
источник