Машина - тьюринг
Cтраница 2
Машины Тьюринга, несмотря на их неадекватность в качестве моделей реальных производственных вычислений, наиболее удобны для исследования вычислительной сложности алгоритмов. Это связано с рядом особенностей их строения и функционирования. [16]
Машина Тьюринга может менять содержимое ленты с помощью специальной читающей и пишущей головки, которая движется вдоль ленты. В каждый момент головка находится в одной из ячеек. Еще надо договориться, с чего мы начинаем и когда кончаем работу. [17]
Машина Тьюринга М - это конечное устройство, которое производит операции на бумажной ленте. [18]
 |
На ленте записаны числа 2 и 3. [19] |
Машина Тьюринга [12-14] аналогична машине Поста. [20]
Машина Тьюринга называется забывчивой ( oblivious), если движение ее головки зависит только от дл-ины входа. [21]
Машина Тьюринга представляет собой алгоритмическую структуру, функционирование которой наиболее естественно описывается с помощью рассмотренной схемы. В роли дискретного преобразователя А выступает головка машины Тьюринга. Роль входного алфавита X автомата А играет внутренний алфавит ленты машины Тьюринга, а в качестве сигналов алфавита Y выступают пары ( я, ттг), где а - символ, который головка записывает в активную ячейку ленты, а т - 1 0, 1 указывает направление движения головки. [22]
Машины Тьюринга 7 и Т % вычисляют примитивно рекурсивные функции Л ( ж) и / 2 ( ж) соответственно. Следует ли отсюда, что композиция Т Тч этих машин вычисляет обязательно примитивно рекурсивную функцию. [23]
Машина Тьюринга может вычислять постоянную функцию с-п ( х) п, запоминая п цифр ответа с помощью внутренних состояний. Вообще говоря, такая машина будет чрезвычайно большой. Например, если п 1010, меньшая машина может дать на выходе 1010 при десятикратном умножении числа 10 самого на себя, а не повторением всех 1010 цифр. [24]
Обычная одноленточная машина Тьюринга [3] состоит из контрольного модуля, головки чтения-записи и бесконечной ленты, разделенной на клетки. Ее поведение определяется конечным набором формул перехода ( обычно называемых пятерками) типа ввод-вывод-сдвиг. [25]
Машину Тьюринга имитирует исполнитель, который в момент t 0 обозревает как начальную ячейку, так и вход граф-схемы. [26]
Машину Тьюринга, выполняющую алгоритм Евклида для чисел, записанных в расширенной двоичной форме, при желании можно получить из EUC с помощью пары дополнительных алгоритмов, которые переводили бы числа из расширенной двоичной формы в унарную и обратно. [27]
Каждая машина Тьюринга соответствует конечному множеству пятерок Q, в котором нет пятерок, начинающихся с двух одинаковых символов. Если такой пятерки в Q нет, то машина останавливается. [28]
Эта машина Тьюринга применима ко всем словам, потому что каждое слово имеет конечную длину, а после пего следуют пустые ячейки. Она будет стирать это слово, если условиться, что когда машина начинает работать, автомат находится против самой левой непустой ячейки. [29]
Если машина Тьюринга способна выполнять единственную, и притом простейшую операцию переработки данных - замену одного символа в ячейке памяти другим символом, то ЭВМ может выполнять гораздо более широкий набор операций. Каждая конкретная ЭВМ имеет свой набор машинных операций: решение любой конкретной задачи в конечном счете должно быть сведено к выполнению последовательности операций из этого набора. Очевидно, что с точки зрения удобства использования машины желательно, чтобы этот набор был возможно шире и чтобы он включал в себя достаточно содержательные операции. С точки же зрения простоты реализации желательно, чтобы этот набор был невелик и чтобы в него входили лишь простейшие операции, так как это позволяет сделать машину более простой, дешевой и надежной. Поскольку эти два требования противоречивы, то выбирается некоторый компромиссный вариант, с учетом того класса задач, на решение которых прежде всего ориентируется данная машина. [30]
Страницы: 1 2 3 4