Можно ли доказать, что функция идемпотентна?

12

Можно ли использовать статические или зависимые типы, чтобы доказать, что функция идемпотентна?

Я безуспешно искал в Google и других местах в StackOverflow / StackExchange ответ. Самым близким, что я нашел, был этот разговор о Идрисе: https://groups.google.com/forum/#!topic/idris-lang/yp7vrspChRg

К сожалению, это обсуждение немного над моей головой.

haskell bmaddy
источник
3
Я не публикую это как ответ, потому что я не уверен на 100%, но я считаю, что это невозможно из-за теоремы Райс .
садовник
4
Это увлекательный вопрос, и моя интуиция показывает, что это должно быть возможно на ограниченном, неполном по Тьюрингу языке. Тем не менее, программисты сосредотачиваются на вопросах, касающихся жизненного цикла разработки программного обеспечения (подробности см. В справочном центре ), тогда как это, кажется, вопрос информатики. Сайт по компьютерным наукам может лучше подходить и привести к лучшим ответам.
Амон
2
@gardenhead Теорема Райса гласит, что, учитывая любое свойство, которое может иметь поведение программы, иногда невозможно определить, есть ли у программы это свойство. Существует большая разница между «это иногда невозможно» и «это невозможно».
Таннер Светт
2
Мой последний комментарий был довольно расплывчатым. В любом случае, вот что говорит теорема Райса: не существует алгоритма, который правильно классифицирует все функции как идемпотентные или не идемпотентные. Однако все еще существуют полезные алгоритмы, которые классифицируют некоторые функции как идемпотентные или нет.
Таннер Светт
2
ОП спросила о том, чтобы доказать, что функция идемпотентна, не имея алгоритма, классифицирующего функции как идемпотент или нет. Основным отличием является то, что доказательство может быть написано человеком. Что касается полноты по Тьюрингу, то это действительно не проблема .
Gallais

Ответы:

3

Для определенных функций это так. Особенно, когда вы знаете функцию ;-)

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

Так что, если это не тот ответ, который вы искали, напишите лучший вопрос, в настоящее время неясно, что именно вы действительно ищете.

Док Браун
источник
Спасибо за ответ. Способность «решать автоматически» была именно тем, что я искал.
Bmaddy
2
Чтобы расширить выражение «для определенных функций это есть» : идемпотентность может быть доказана для любой функции, которая либо принимает только конечное количество входных данных (опробовав все из них), либо тип входных данных, который определяется рекурсивно (например, натуральный). числами или связанными списками), что означает, что вам нужно только доказать, что идемпотентность верна для базового (-ых) случая (-ов) и рекурсивного (-ых) случая (-ов).
Qqwy