Jump to content

Конструктивная функция

(Перенаправлено с Space Constructible )

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

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

[ редактировать ]

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

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

Определения, конструируемые в пространстве

[ редактировать ]

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

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

Все часто используемые функции f ( n ) (такие как n , n к , 2 н ) конструируемы во времени и пространстве, пока f ( n ) равна по крайней мере cn для константы c > 0. Никакая функция, равная o ( n ), не может быть конструируема во времени, если она в конечном итоге не является постоянной, поскольку недостаточно время прочитать весь ввод. Однако — пространственно-конструируемая функция.

Приложения

[ редактировать ]

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

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

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

  1. ^ Перейти обратно: а б с Гольдрейх, Одед (2008). Вычислительная сложность: концептуальная перспектива . Издательство Кембриджского университета. стр. 130, 139. ISBN.  978-0-521-88473-0 .
  2. ^ Перейти обратно: а б Гомер, Стивен; Селман, Алан Л. (2011). Теория вычислимости и сложности (второе изд.). Спрингер. ISBN  978-1-4614-0681-5 .
  3. ^ Балькасар, Хосе Луис; Диас, Джозеф; Габарро, Хоаким (1988). Структурная сложность I. Спрингер-Верлаг. ISBN  3-540-18622-0 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 8a597f3d9ba3df7f96a0cb36dc8f1bd8__1715762040
URL1:https://arc.ask3.ru/arc/aa/8a/d8/8a597f3d9ba3df7f96a0cb36dc8f1bd8.html
Заголовок, (Title) документа по адресу, URL1:
Constructible function - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)