Конструируемая функция - Constructible function

В теория сложности, а временная функция это функция ж из натуральные числа к натуральным числам со свойством, что ж(п) можно построить из п по Машина Тьюринга во время заказа ж(п). Целью такого определения является исключение функций, которые не обеспечивают верхнюю границу времени выполнения некоторой машины Тьюринга.^[1]

Конструируемые во времени определения

Есть два разных определения функции, конструируемой во времени. В первом определении функция ж называется конструктивный если существует положительное целое число п₀ и машина Тьюринга M который, учитывая строку 1^п состоящий из п один, останавливается ровно через ж(п) шаги для всех п ≥ п₀. Во втором определении функция ж называется конструктивный если существует машина Тьюринга M который, учитывая строку 1^п, выводит двоичное представление ж(п) в О (ж(п)) время (вместо этого можно использовать унарное представление, так как они могут быть взаимно преобразованы в О(ж(п)) время).^[1]

Также существует понятие полностью конструируемой во времени функции. Функция ж называется полностью построенный во времени если существует машина Тьюринга M который, учитывая строку 1^п состоящий из п один, останавливается ровно через ж(п) шаги. Это определение немного менее общее, чем первые два, но для большинства приложений можно использовать любое определение.^{[нужна цитата ]}.

Пространственно-конструктивные определения

Аналогично функция ж является конструктивный если существует положительное целое число п₀ и машина Тьюринга M который, учитывая строку 1^п состоящий из п единицы, останавливается после использования ровно ж(п) клетки для всех п ≥ п₀. Эквивалентно функция ж является конструктивный если существует машина Тьюринга M который, учитывая строку 1^п состоящий из п единица, выводит двоичное (или унарное) представление ж(п), используя только О (ж(п)) Космос.^[1]

Также функция ж является полностью космический если существует машина Тьюринга M который, учитывая строку 1^п состоящий из п единицы, останавливается после использования ровно ж(п) клетки^{[нужна цитата ]}.

Примеры

Все часто используемые функции ж(п) (Такие как п, п^k, 2^п) конструктивны во времени и пространстве, пока ж(п) не менее сп для постоянного c > 0. Нет функции, которая о (п) может быть конструируемым во времени, если только он не станет в конечном итоге постоянным, поскольку времени для чтения всего ввода недостаточно. Тем не мение, ${\displaystyle \log(n)}$ является пространственно-конструктивной функцией.

Приложения

Функции, построенные по времени, используются в результатах теории сложности, таких как теорема об иерархии времени. Они важны, потому что теорема иерархии времени опирается на машины Тьюринга, которые должны определять в О (ж(п)) время, потраченное на выполнение алгоритмом более ж(п) шаги. Это, конечно, невозможно без возможности вычислить ж(п) в то время. Такие результаты обычно верны для всех естественных функций. ж но не обязательно верно для искусственно построенных ж. Чтобы сформулировать их точно, необходимо точное определение для естественная функция f для которых верна теорема. Для такого определения часто используются конструируемые во времени функции.

Аналогично используются пространственно-конструктивные функции, например, в теорема пространственной иерархии.

Эта статья включает в себя материал из конструктива на PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.

Рекомендации

1. Гольдрайх, Одед (2008). Вычислительная сложность: концептуальная перспектива. Издательство Кембриджского университета. С. 130, 139. ISBN  978-0-521-88473-0.