Cтраница 1
Многоленточная машина Тьюринга имеет конечное число рабочих лент, на каждой из которых находится по одной головке, и отдельную входную ленту с только читающей головкой с двусторонним движением. Рабочие ленты бесконечны вправо и влево. Первоначально рабочие ленты пусты, а головка на входной ленте расположена на крайне левом символе входного слова. Машина допускает входное слово, приходя в допускающее состояние и останавливаясь. [1]
Многоленточная машина Тьюринга со входом работает в реальном масштабе времени, если все ее состояния голосующие. Хорошо известно, что ограничение реального времени очень сильно суживает возможности машины Тьюринга. [2]
Многоленточная машина Тьюринга со входом М начинает вычисление в фиксированном состоянии s0 ( принадлежащем к алфавиту состояний) с пустыми лентами. Входные символы М образуют входной алфавит, выходные символы - выходной алфавит. В ответ на входной символ машина вырабатывает соответствующий выходной символ. Такой ответ не обязательно должен следовать непосредственно вслед за восприятием соответствующего входного символа: машина может предварительно совершить несколько шагов в процессе своей работы. [3]
Поэтому многоленточная машина Тьюринга оказывается более реальной моделью, когда и стремится к бесконечности. [4]
Часто рассматривают многоленточные машины Тьюринга. Построение таких машин основывается на следующей общей идее, справедливой для произвольных преобразователей. [5]
Спрашивающей машиной называется многоленточная машина Тьюринга с одной выделенной лентой, называемой лентой вопросов, и тремя выделенными состояниями, называемыми соответственно спрашивающим состоянием, да-состоянием и нет-состоя-наем. Мы можем понимать под оракулом того, которому известно Т и который переводит М в да-состояние или нет-состояние. [6]
Аналогично можно рассматривать многоленточные машины Тьюринга, а также машины Тьюринга с неколькими головками. [7]
В начале работы многоленточной машины Тьюринга все ленты пусты, кроме входной, на которой записан вход. [8]
Генератор последовательностей - это многоленточная машина Тьюринга, у которой с некоторыми состояниями управляющего устройства связаны выходные символы. Он начинает свою работу в некотором выделенном начальном состоянии и с пустыми лентами. В процессе своей работы он иногда попадает в состояния, с которыми связаны выходные символы. Последовательность ( бесконечная) этих выходных символов называется порождаемой этой машиной последовательностью. Бесконечная последовательность w называется Т ( п) - вычислимой тогда и только тогда, когда существует некоторый генератор последовательностей М, который выдает / г-й член w за Т ( п) или меньше операций. [9]
Наиболее часто используемые модели вычислительных устройств - это одноленточные и многоленточные машины Тьюринга и машины с произвольным доступом к памяти. [10]
ST) тогда и только тогда, когда существует многоленточная машина Тьюринга, порождающая а так, что ап печатается не более чем за Т ( п) операций. Темой этой статьи является сложность классов ST, где Т - вычислимая монотонная функция. [11]
Теорема 1.4. РАМ и РАСП с логарифмическим весом и многоленточные машины Тьюринга полиномиально связаны. [12]
Каждая детерминированная t ( n) - ограниченная по времени многоленточная машина Тьюринга моделируется альтернирующей ( t ( n) og log t ( n) / og t ( n)) - огранич нной по времени машиной Тьюринга. [13]
Приводится нижняя оценка вида cN log N для временной сложности многоленточной машины Тьюринга, выполняющей умножение в темпе поступления информации / V-разрядных бинарных целых чисел. [14]
Так же как и генератор последовательностей, машина Тьюринга со входом является многоленточной машиной Тьюринга, выходы которой связаны с состояниями управляющего устройства. Кроме того, машина со входом имеет специфический ввод входной информации. Машина начинает работать в фиксированном начальном состоянии и с пустыми лентами. После восприятия входного символа она производит некоторое число операций, пока не попадает в состояние, с которым связан выход. После этого машина готова воспринять следующий входной символ, и процесс повторяется. [15]