Жизнь без CONS

Могут ли функциональные программы высшего порядка решить больше задач, чем программы первого порядка? Ответ: НЕТ, поскольку оба класса программ являются полными по Тьюрингу. Причина в том, что значения высшего порядка могут быть смоделированы значениями первого порядка: используйте «замыкания» функций, построенные конструктором списка «CONS». Теория сложности характеризует выразительную мощность программ «без cons» с различными порядками данных и структурами управления. Мы точно характеризуем задачи типа [Bool]- Bool, разрешимые программами относительно ДАННЫХ: наличие или отсутствие конструкторов и типов данных (порядок 0, 1 или выше); и УПРАВЛЕНИЯ: общая рекурсия, хвостовая рекурсия, примитивная рекурсия. Пример для программ первого порядка без cons: общая рекурсия мощнее примитивной рекурсии (например, «fold») тогда и только тогда, когда PTIME корректно содержит LOGSPACE. (Это давняя открытая проблема в области сложности.) Программы второго порядка, не содержащие констант, мощнее программ первого порядка: функция типа [Bool]- Bool принадлежит классу PTIME тогда и только тогда, когда она вычислима как функция первого порядка, не содержащая констант; и классу EXPTIME тогда и только тогда, когда она вычислима как функция второго порядка, не содержащая констант. (Известно, что PTIME является строго меньшим классом, чем EXPTIME.) Кроме того, детерминированные программы, не содержащие констант, характеризуют иерархию сложности. Программы с порядком данных 0, 1, 2, ... могут решать именно эти задачи: PTIME EXPTIME EXP2TIME ... ЭЛЕМЕНТАРНАЯ, Что произойдет, если мы добавим НЕдетерминизм? Используя некоторые хитрые методы программирования с функциями первого порядка в качестве данных, Коп и Симонсен получают удивительный результат (2017), что эта иерархия «коллапса» на втором порядке: PTIME НАЧАЛЬНАЯ ШКОЛА = НАЧАЛЬНАЯ ШКОЛА = ... = НАЧАЛЬНАЯ ШКОЛА Подробнее об этом видео смотрите по ссылке: https://www.microsoft.com/en-us/resea...