Cтраница 2
Множество слов R называется Т ( I) - допустимым, если существует многоленточная машина Тьюринга, которая допускает множество R и для входов длины / использует не более Т ( 1) операций. [16]
Теорема 7.12. В классе LA ( / - распознавателей существует алгоритм синтаксического распознавания на многоленточной машине Тьюринга, требующий времени, пропорционального длине входного слова. [17]
Настоящая работа, которая является попыткой построить математическую модель для цифровых машин, касается класса многоленточных машин Тьюринга, которые с некоторыми ограничениями применяются для вычислений некоторого класса функций в реальное время. Употребляя цифровую вычислительную машину, важно знать время, необходимое для вычисления данной функции. [18]
Применяя описанный прием расширения вычислительных сред в случае одноленточной машины Тьюринга, приходим к понятию многоленточной машины Тьюринга. Так, / г-ленточной машиной Тьюринга называется конечный преобразователь, вычислительной средой которого является вектор синтаксических сред, размерности k ( k лент), а операторы состоят из вектора операторов одноленточной машины Тьюринга. Оператор, записанный в i-и компоненте вектора операторов, применяется к 1 - й ленте. Вначале работы одна основная лента заполнена, а остальные пусты. [19]
Целью данной статьи является описание схемы, при помощи которой двуленточная машина Тьюринга за nlogn операций может имитировать работу многоленточной машины Тьюринга, произведенную за п операций. По сравнению со схемой, использующей одну ленту, эта схема позволяет улучшить соответствующие результаты, получаемые при помощи диагонального метода. Такие приложения будут рассмотрены в последующих разделах. [20]
В [8] показано, что каждый бесконтекстный язык является ( Т ( п) п3) - распознаваемым на многоленточной машине Тьюринга. [21]
Параметр п относится к размеру входа, а временные оценки суть оценки времени в худшем случае и относятся к многоленточной машине Тьюринга ( или любой разумной машине с произвольным доступом к памяти), за исключением случаев, где это будет специально оговариваться. [22]
Эта статья продолжает исследование ( начало которому положили Хартманис и Стирнз [1]) вычислительной сложности двоичных последовательностей, порождаемых многоленточными машинами Тьюринга. На ленте могут быть символы лишь из конечного множества, а управляющее устройство может находиться только в конечном числе внутренних состояний. Машинная операция полностью определяется состоянием процессора и символами, находящимися под головками на лентах, и состоит в печатании символов в каждой из ячеек под головками, сдвигании каждой из лент самое большее на одну ячейку в любом направлении и изменении состояния процессора. Исходя из некоторого начального состояния и набора пустых лент, машина порождает двоичную последовательность на специальной односторонней выходной ленте. [23]
Если глубина каждого направленного ациклического графа с п ребрами может быть приведена к log n удалением только о ( п) ребер, то недетерминированные многоленточные машины Тьюринга за линейное время могут распознавать языки, не распознаваемые детерминированными многоленточными машинами Тьюринга за такое же время. Для некоторых графов уменьшение глубины до log п требует удаления Q ( / z / log log п) ребер. Дается теоретико-графовое условие того, что забывчивость ( obliviousness) уменьшает мощность многоленточных машин Тьюринга. [24]
Если глубина каждого направленного ациклического графа с п ребрами может быть приведена к log n удалением только о ( п) ребер, то недетерминированные многоленточные машины Тьюринга за линейное время могут распознавать языки, не распознаваемые детерминированными многоленточными машинами Тьюринга за такое же время. Для некоторых графов уменьшение глубины до log п требует удаления Q ( / z / log log п) ребер. Дается теоретико-графовое условие того, что забывчивость ( obliviousness) уменьшает мощность многоленточных машин Тьюринга. [25]
Наш вклад по отношению к [3] состоит, во-первых, в том, что основная линия доказательства несколько короче и проще, во-вторых, нижняя оценка, приводимая в [3], увеличена на множитель log log я и, как показано, она справедлива и для среднего и для максимального времени, в-третьих, намечен новый путь исследований, который позволит получить даже более сильный результат для класса многоленточных машин Тьюринга. [26]
Это равносильно вопросу, что именно является правильной моделью компьютера для измерения времени работы алгоритма. Обычно в литературе используют многоленточные машины Тьюринга, но им лрисущи искусственные ограничения с точки зрения эффективной, реализации алгоритмов. [27]
Набор элементарных инструкций у описанных выше машин Тьюринга крайне беден. Имеются разнообразные их обобщения, например, многоленточные машины Тьюринга. В отличие от описанной выше, такая МТ имеет несколько ( конечное множество) лент, каждая со своей головкой, управляющему устройству доступны символы, находящиеся в ячейках, на которых расположены головки лент. Выделены две ленты: входная, с которой разрешается только читать символы, и выходная, на которую разрешается только писать символы. Остальные ленты называются рабочими. Многоленточная машина называется fc - ленточной, если у нее k рабочих лент. Это действие однозначно определяется состоянием управляющего устройства и набором символов в ячейках под головками. Если действие выполнить нельзя, машина останавливается. [28]
Для уточнения введенных понятий необходима некоторая модель вычислений. В качестве такой модели может быть выбрана многоленточная машина Тьюринга. Она состоит из k лент, бесконечных справа. Каждая лента разбита на ячейки, которые содержат по одному символу из некоторого набора. [29]
Одной из частей машины Ми будет устройство ( многоленточная машина Тьюринга с записью на ленте), которое вычисляет в реальное время функцию U ( n), причем если это устройство начинает свою работу, используя записанные на одной из лент машины Ми п символов, то эта работа должна закончиться за время, не превосходящее C U ( ri), после чего на другой ленте Ми должны быть записаны U ( n) символов. [30]