Нечаянные вычислители
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 11.03.17 21:45
Оценка: 96 (7) :)))
Под "нечаянными вычислителями" я подразумеваю ситуации, когда разработчики языка или рантайма хотели как лучше, а получилось нечто, с побочными эффектами в виде способности решать вычислительные задачи там, где этого изначально не предполагалось. Навскиду вспомнились:

Тьюринг-полнота:

систем типов Scala, Haskell, Rust;
ассемблерной инструкции mov;
дженериков Java;
C-препроцессора (с рядом оговорок).

Возможность решения NP-полной задачи 3-SAT с помощью механизма разрешения перегрузок в C#.

---

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

UPD: в комментах на фейсбуке подсказали ещё пару ссылок: https://www.gwern.net/Turing-complete и http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html Что касается полноты по Тьюрингу языков или их составных частей:

XSLT/XQuery;
Sed Script;
механизм обработки ошибок MMU;
шаблоны C++;
HTML5+CSS3;
SQL;
правила перезаписи URL mod_rewrite;
язык шаблонов MediaWiki
SSI;
правила перезаписи sendmail;
язык формул в Excel.

UPD: формат релокаций в ELF-файлах также полон по Тьюрингу.
UPD: Nikov на FB подсказывает, что ещё и система типов TypeScript полна по Тьюрингу.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Отредактировано 25.03.2017 22:25 kochetkov.vladimir . Предыдущая версия . Еще …
Отредактировано 12.03.2017 12:29 kochetkov.vladimir . Предыдущая версия .
Отредактировано 11.03.2017 23:50 kochetkov.vladimir . Предыдущая версия .
Отредактировано 11.03.2017 23:49 kochetkov.vladimir . Предыдущая версия .
Отредактировано 11.03.2017 21:50 kochetkov.vladimir . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.