Когда можно сказать, что две программы разные?

Q1. Когда можно сказать, что две программы (написанные на каком-то языке программирования, например C ++) различны?

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

Q2. Являются ли программы и алгоритмы одним и тем же объектом? Если нет, каково определение алгоритма и чем оно отличается от определения программы? Когда можно сказать, что два алгоритма эквивалентны?

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

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

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

Это не крайность: эквивалентность программы должна быть определена относительно понятия наблюдения.

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

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

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

По сути, не существует единого понятия эквивалентности программ; оно всегда связано с понятием наблюдения, которое вы выбираете, и это зависит от приложения, которое вы имеете в виду.

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

Извините, если это наивно. Я не занимаюсь исследованиями PL.