Логика в информатике cs.LO

В мире логики есть мост. Он перекинут через пропасть, разделяющую допустимость правила и его выводимость из аксиом. Пока правила обходятся конечным числом посылок, мост крепок — для классической логики всё, что не нарушает истинность, уже содержится в синтаксисе. Но стоит добавить бесконечные посылки, и опоры начинают дрожать. Мост, увы, не всесилен.

Осень 1956 года. Курт Гёдель выводит на листе бумаги вопрос, обращённый к умирающему Джону фон Нейману: можно ли проверить выполнимость булевой формулы быстрее, чем полным перебором? Ответ придёт через 69 лет — и окажется укусом логического уробороса, мифического змея, поедающего собственный хвост. Змей рождается из случайности.

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