Геометрическая интерпретация вычислений

Будучи из физики, я был обучен изучать множество проблем с геометрической точки зрения. Например, дифференциальная геометрия многообразий в динамических системах и т. Д. Когда я читаю основы информатики, я всегда пытаюсь найти геометрические интерпретации. Как правдоподобная геометрическая интерпретация рекурсивно перечислимых множеств (я работал над частью, где пытался связать их с алгебраической геометрией, используя эквивалентность с диофантовыми множествами, но связь казалась вынужденной, и я не мог найти «естественное» выражение фактов в этом формулировка) или красивый геометрический результат для простого алгоритма сортировки чисел. Хотя я не эксперт, я читал обзоры по теории геометрической сложности, и это, безусловно, интересная программа, но меня больше интересует геометрическое представление о чрезвычайно фундаментальных понятиях, таких как динамика машины Тьюринга, лямбда-исчисление или структура ( un) вычислимые множества (а не конкретные задачи). Поиск безнадежной геометрической структуры в этих объектах - это безнадежная работа, или можно ожидать каких-то запутанных результатов? Есть ли формулировка TCS, которая рассматривает это геометрически?

Семантика компьютерных программ может быть понята геометрически тремя различными (и явно несовместимыми) способами.

• Самый старый подход - с помощью теории предметной области . Интуиция, лежащая в основе теории предметной области, проистекает из асимметрии терминации и нетерминации.

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

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

  Лучшее топологическое введение, которое я знаю об этих идеях, - короткая и чрезвычайно доступная топология Стива Викерса с помощью логики . Это можно понимать как своего рода разогрев значительно более грозных каменных пространств Питера Джонстона .

  Если вы ищете онлайн лекционные заметки, позвольте мне предложить Синтетическую топологию типов данных и классических пространств Мартина Эскардо .

• Другая точка зрения вытекает из теории параллелизма. Параллельная программа может пониматься как наличие нескольких допустимых исполнений (последовательностей состояний), в зависимости от того, как разрешены гонки. Затем набор исполнений можно рассматривать как пространство, причем каждая возможная последовательность состояний понимается как путь через это пространство. Затем методы из алгебраической топологии и гомотопической теории могут быть применены для получения инвариантов о выполнении программы.

  Нир Шавит и Морис Херлихи используют эту идею, чтобы доказать невозможность некоторых распределенных алгоритмов, за которые они выиграли приз Геделя 2004 года. (См . Топологическую структуру асинхронных вычислений .) У Эрика Губо есть обзорный документ, объясняющий соответствующие идеи в « Некоторые геометрические перспективы в теории параллелизма» .

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

  См. Ссылку Коди выше на книгу по теории гомотопических типов .

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

Как это и произошло, в последнее время появилась теория зависимых типов , в которой типы, которые традиционно представляют статический инвариант для компьютерной программы, могут интерпретироваться как топологическое пространство или, скорее, класс эквивалентности таких пространства ( гомотопический тип ).

За последние несколько лет это стало предметом интенсивных исследований, кульминацией которых стала книга .

$\lambda$

Вам известно о GCT, но, возможно, вы не знаете о более ранней работе Малмулей по демонстрации разделения между подмножеством PRAM-вычислений и P, в котором используются геометрические представления о том, как вычисление можно рассматривать как деление пространства.

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

В каком-то смысле, ВСЕ оптимизация является геометрической: линейные программы включают в себя нахождение нижней точки многогранника в больших измерениях, SDP - это линейные функции в пространстве полуопределенных матриц и т. Д. Геометрия широко используется при разработке алгоритмов здесь.

По этой теме существует длинная и глубокая связь между нашей способностью оптимизировать определенные функции на графах и нашей способностью внедрять метрические пространства в определенные нормированные пространства. Это огромная литература сейчас.

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

$T_1$

Один из способов понять взаимосвязь между обработкой информации (также известной как «вычисление») и геометрией состоит в том, что обработке информации предшествует геометрия. Эта точка зрения должна быть знакома с некоторыми частями физики. Например, в теории относительности мы изучаем как причинную структуру пространства-времени (его обработку информации), так и его геометрическую структуру . Многие сочли бы, что последний является более простым, чем первый.

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

Ссылки:

• Вычислительные структуры для моделирования пространства, времени и причинности , семинар Dagstuhl 06341, 20–25 августа 2006 г.

• Ки Мартин и Пракаш Панангаден: геометрия пространства-времени из причинно-следственной структуры и измерения

$U$ эквивалентно нахождению короткой геодезической в ​​конкретной криволинейной геометрии. Подробности см. В следующих документах: http://arxiv.org/abs/quant-ph/0603161 и http://arxiv.org/abs/quant-ph/0701004.

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

• Апериодическая черепица плоскости и черепица Пенроуза . Доказано, что вопрос о наличии аперодической плитки на плоскости неразрешим.

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

• $(x,y)$ множестве Мандельброта ?

• Неразрешимость в динамических системах (Хейнри), опять же, иногда тесно связана с физикой. Динамические системы обычно имеют многомерную геометрическую интерпретацию.

• Языки визуального программирования . программу можно рассматривать как тип (ориентированного?) графа с разными типами вершин (например, условная, арифметическая операция) и т. д.