«Категория» машин Тьюринга?

16

Отказ от ответственности: я очень мало знаю о теории сложности.

Извините, но на самом деле нет способа задать этот вопрос, не будучи (ужасно) лаконичным:

Какими должны быть морфизмы в «категории» машин Тьюринга?

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

Я хотел бы подчеркнуть, что я ищу категорию машин Тьюринга, а не формальных языков, например. В частности, я думаю, что мои морфизмы должны содержать более точную информацию, чем сокращения или что-то подобное (хотя я не уверен).

Конечно, если в литературе уже есть хорошо известная и используемая категория, я бы хотел знать, что это такое.

Саал Хардали
источник
3
Вы сами сказали - вычислимые функции.
Юваль
1
@ Рафаэль, дело в том, что вы никогда не определяете структуру, пока не поместите ее в категорию. Именно тогда несущественные особенности конкретного определения отбрасываются.
Саал Хардали
1
@ SaalHardali Имейте в виду, что не все подписываются на обещание спасения, данное теоретиками категорий. На самом деле многие закатывают глаза.
Рафаэль
2
@ JoshuaGrochow Существует морфизм, помеченный от T 1 до T 2, если f уменьшает T 2 до T 1 (или, возможно, наоборот), то есть T 1 ( x ) = T 2 ( f ( x ) ) . Это, скажем, для машин, которые на каждом входе либо останавливаются, либо нет, но не имеют дальнейшего вывода. fT1T2fT2T1T1(x)=T2(f(x))
Юваль
3
В сторону: почему ТМ должны быть объектами? Они также могут быть морфизмами.
Мартин Бергер

Ответы:

11

Саал Хардали отметил, что он хотел, чтобы категория машин Тьюринга занималась геометрией (или, по крайней мере, теорией гомотопии). Тем не менее, есть много разных способов достижения похожих целей.

  • Существует очень сильная аналогия между вычислимостью и топологией. Интуиция заключается в том, что завершение / нетерминация подобны пространству Серпинского, поскольку окончание является конечно наблюдаемым (то есть открытым), а нетерминация - нет (не открытым). См. Примечания к лекции Мартина Эскардо. Синтетическая топология типов данных и классических пространств для умеренно нежного, но всестороннего введения в эти идеи.

  • В параллельных и распределенных вычислениях часто полезно думать о возможных выполнениях программы как о пространстве, и тогда различные ограничения синхронизации могут быть выражены как гомотопические свойства пространства. (Тот факт, что исполнение имеет временной порядок, по-видимому, требует направленной теории гомотопий, а не обычной теории гомотопий.)

    См. Статью Эрика Губо « Некоторые геометрические перспективы теории параллелизма» для более подробной информации. Также см. Статью Мориса Херлихи и Нира Шавита, удостоенную премии Гёделя, «Топологическая структура асинхронной вычислимости» , в которой решены некоторые давние открытые проблемы в теории распределенного программирования.

  • Третья идея приходит через теорию гомотопического типа, благодаря открытию, что теория типа Мартина-Лёфа является (вероятно?) Синтаксическим представлением (в смысле образующих и отношений) теории омега-группоидов - то есть моделей абстрактного гомотопическая теория. Лучшее введение в эти идеи - книга по теории гомотопических типов .

Обратите внимание, что все эти идеи сильно отличаются друг от друга, но все еще используют геометрические интуиции! И есть еще другие, которые я не знаю, такие как использование, возникающее в геометрической теории сложности, и способ, которым теории цепей могут быть описаны в терминах (со) гомологии теории графов .

По сути, когда вы делаете CS, геометрия является инструментом - вы используете его для формализации своей интуиции, чтобы вы могли получить рычаги за счет огромного объема работы, которая была проделана над ней. Но это усилитель идеи, а не замена идеи!

Нил Кришнасвами
источник
14

Если ваши объекты являются машинами Тьюринга, есть несколько разумных возможностей для морфизмов. Например:

1) Рассматривайте машины Тьюринга как автоматы, которыми они являются, и рассматривайте обычные морфизмы автоматов (карты между алфавитами и состояниями, которые согласуются друг с другом), которые также либо сохраняют движения головки (голов) ленты, либо точно обратные их (например, всякий раз, когда исходная ТМ идет налево, целевая ТМ идет направо и наоборот).

2a) Рассмотрите симуляции или бисимуляции .

T1T2fT1(x)=T2(f(x))x

3) Рассмотрим граф переходов машины Тьюринга (каждая вершина представляет собой полное описание состояния машины и лент с направленными ребрами, соответствующими переходам, которые должна выполнять ТМ), и рассмотрим морфизмы графов. Однако для ТМ это очень грубое отношение, поскольку оно по существу игнорирует локальную природу вычислений (например, игнорируется, каково содержимое лент).

Я думаю, что настоящий вопрос заключается в следующем: что вы хотите знать о ТМ или делать с ними? В отсутствие этого трудно приводить аргументы для какого-либо одного определения над другим, за пределами естественности (в обычном смысле этого слова, а не в категориальном смысле).

Джошуа Грохов
источник
Я очень новичок в этом виде математики. В прошлом я читал о теории сложности, но только недавно я снова поднял ее после того, как увидел в Интернете кого-то, кто утверждал, что каким-то образом когомологические методы войдут в теорию сложности в следующем столетии, и это меня заинтересовало. После некоторого прочтения я понял, что помимо поверхностного понимания определения машины Тьюринга, я в принципе не представляю, что именно она кодирует. Вот так я и пришел к вопросу. Таким образом, вы можете сказать, что на очень элементарном уровне я пытаюсь представить, как когомологии могут войти в теорию сложности.
Саал Хардали
Я понимаю, что это крайне преждевременно для такого человека, как я, который очень мало разбирается в этой теме, и все же я хотел немного поиграть с этой идеей в своей главе «Создание теории гомотопий в категории машин Тьюринга». Ваш ответ хорош, и я, конечно, стремлюсь узнать больше о его аспектах. Спасибо.
Саал Хардали
@ SaalHardali: мне любопытно, когда вы читаете, что когомологии войдут в теорию сложности? Я могу придумать два пути, но я пока не вижу пути с помощью теории гомотопических типов (возможно, потому, что я еще недостаточно хорошо понимаю HoTT). Два способа, которые я вижу: (1) в распределенных вычислениях это уже произошло, а именно. Herlihy и Rajsbaum, и (2) с помощью геометрической теории сложности.
Джошуа
По теории гомотопии я ссылался на общую идею изучения категорий со слабыми эквивалентностями и не так много HoTT. Я прочитал это в опросе о P =? NP, это не трудно найти, я думаю, что это было связано с одним из вопросов на этом сайте. Думаю, мое первое предположение (как постороннего) заключалось в том, что, возможно, существует некоторая интересная слабая эквивалентность в некоторой категории модели вычислений, которая каким-то образом соответствует классам сложности, и затем изучение функторов, инвариантных относительно этой слабой эквивалентности, будет составлять то, что я называю " теория гомотопии "это, вероятно, очень наивно и, тем не менее, полностью пропущено.
Саал Хардали
Если вас интересует теория сложности, а не теория вычислимости, возможно, этот ответ вам полезен: cstheory.stackexchange.com/a/3422/4896
Сашо Николов
13

Вас могут заинтересовать категории Тьюринга Робина Кокетта и Питера Хофстра. С точки зрения теории категорий на вопрос «что категория машин Тьюринга» менее интересен , чем «что категорический структура , которая лежит в основе вычислений». Таким образом, Робин и Питер идентифицируют общий вид категории, которая подходит для разработки теории вычислимости. Тогда есть несколько возможностей для определения такой категории, начиная с машин Тьюринга. Зачем иметь одну категорию, если вы можете иметь целую категорию из них?

Андрей Бауэр
источник