Исследуется ли построение на основе constexpr Turing?

Ответ 1

tl; dr: constexpr в С++ 11 не был завершен Turing из-за ошибки в спецификации языка, но эта ошибка была рассмотрена в последующих черновиках стандарта, а clang уже реализует исправить.

constexpr, как указано в международном стандарте ISO С++ 11, не является завершением Turing. Доказательство эскиза:

• Результат constexpr f функции f (или не завершение) для определенной последовательности аргументов a... определяется только значениями a...
• Каждое значение аргумента, которое может быть сконструировано внутри константного выражения, должно иметь буквенный тип, который под [basic.types]p10 равен:
  • скалярный тип,
  • ссылка,
  • массив типа literal или
  • тип класса
• Каждый из указанных случаев имеет конечный набор значений.
  • Для скалярного, не указательного типа это следует тривиально.
  • Для указателя или ссылки, которые будут использоваться в константном выражении, он должен быть инициализирован выражением адреса или ссылки константы, поэтому он должен ссылаться на объект со статической продолжительностью хранения, из которого в любой программе имеется только конечная величина.
  • Для массива граница должна быть константой, и каждый член должен быть инициализирован константным выражением, из которого следует результат.
  • Для типа класса существует конечное число членов, и каждый член должен быть буквенного типа и инициализирован константным выражением, из которого следует результат.
• Следовательно, множество возможных входов a..., которое может принимать f, конечно, поэтому любая конечно-описанная система constexpr является конечной машиной конечного состояния и, таким образом, не является Тьюрингом.

Однако, начиная с публикации стандарта С++ 11, ситуация изменилась.

Проблема, описанная в Johannes Schaub, отвечает на std:: max() и std:: min() not constexpr, была сообщена Комитету по стандартизации С++ в качестве основной проблемы 1454. На совещании WG21 в феврале 2012 года мы решили, что это был дефект стандарта, и выбранная резолюция включала возможность создания значений типов классов с указателями или ссылочными элементами, которые обозначают временные. Это позволяет накапливать и обрабатывать неограниченное количество информации с помощью функции constexpr и достаточно, чтобы оценка constexpr Turing-complete (предполагая, что реализация поддерживает рекурсию на неограниченную глубину).

Чтобы продемонстрировать Turing-полноту constexpr для компилятора, который реализует предлагаемое разрешение основной проблемы 1454, я написал симулятор Turing-machine для набора тестов clang:

http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp

Базовые версии обоих g++ и clang реализуют разрешение этой основной проблемы, но реализация g++ в настоящее время не может обработать этот код.

Ответ 2

Посмотрите на них. Я собрал примеры, и они работают в GCC 4.6: Расчеты времени компиляции, Разбор строк во время компиляции - часть I, Разбор строк во время компиляции - Часть II

Ответ 3

Если мы возьмем ограничения учетной записи реального компьютера, такие как конечная память и конечное значение MAX_INT, то, конечно, constexpr (а также весь С++) не является завершением Turing.

Но если мы удалим это ограничение - например, если мы будем думать о int как вполне суровое положительное целое число - тогда да, constexpr часть С++ будет завершена. Легко выразить любую частичную рекурсивную функцию.

0, S (n) = n + 1 и селекторов I_n ^ m (x_1,..., x_n) = x_m, и суперпозиция, очевидно, может быть выражена с использованием constexpr.

Примитивная рекурсия может быть выполнена прямо:

constexpr int h(int x1, ..., int xn, int y) {
  return (xn == 0) ? f(x1, ..., xn) : g(x1, ..., xn, y-1, h(x1, ..., xn, y-1));
}

И для частичной рекурсии нам нужен простой трюк:

constexpr int h(int x1, ... int xn, int y = 0) {
  return (f(x1, ... xn, y) == 0) ? y : h(x1, ..., xn, y+1);
}

Таким образом, мы получаем любую функцию частичной рекурсии как constexpr.