Лента - машина - тьюринг
Cтраница 3
Машина Тьюринга представляет собой алгоритмическую структуру, функционирование которой наиболее естественно описывается с помощью рассмотренной схемы. В роли дискретного преобразователя А выступает головка машины Тьюринга. Роль входного алфавита X автомата А играет внутренний алфавит ленты машины Тьюринга, а в качестве сигналов алфавита Y выступают пары ( я, ттг), где а - символ, который головка записывает в активную ячейку ленты, а т - 1 0, 1 указывает направление движения головки. [31]
В самой ранней работе по анализу алгоритмов определена вычислимость алгоритма в машине Тьюринга. При анализе подсчитывается число переходов, необходимое для решения задачи. Анализ пространственных потребностей алгоритма подразумевает подсчет числа ячеек в ленте машины Тьюринга, необходимых для решения задачи. Такого рода анализ разумен, и он позволяет правильно определить относительную скорость двух алгоритмов, однако его практическое осуществление чрезвычайно трудно и занимает много времени. Сначала нужно строго описать процесс выполнения функций перехода в машине Тьюринга, выполняющей алгоритм, а затем подсчитать время выполнения - весьма утомительная процедура. [32]
 |
Путь вычислений. [33] |
Термин слово, с другой стороны, означает последовательность символов, записанную на ленте в данный момент. Такая последовательность должна всегда иметь конечную длину. В большинстве случаев будет необходимо ссылаться только на слово, записанное на ленте машины Тьюринга перед началом вычислений. Тогда мы будем говорить о начальной ленте и входном слове, которое она содержит. Когда описываются вычисления на машинах Тьюринга, удобно считать, что считывающая головка движется по ленте, а лента остается неподвижной. [34]
Пользуясь методами § 68, мы можем построить машину Тьюринга, которая будет находить р4 () - ую клетку, отправляясь от - ой, если на 0 - й ( или - 1 - й) клетке постоянно имеется отличительная пометка. Вычисления, выполняемые для этой цели, могут производиться с помощью пометок, которые впоследствии будут стерты, причем за это время на них ничего не будет печататься. Это позволяет нам свести вычисление в данном пространстве символов к вычислению на линейной ленте машины Тьюринга. Это имеет место в любом обычном пространстве символов. Исключение представляет вычислитель, принимающий время от времени сигналы на слух. Пространство символов может состоять из нескольких разобщенных подпространств, в каждом из которых имеется своя воспринимаемая ячейка, как, например, в случае вычислителя, который одновременно глазами читает на бумаге символ, ощупью находит на ленте другой и получает на слух сигнал. Если имеется г таких подпространств, мы можем перестроить ячейки так, чтобы они были наборами из г ячеек, по одной в каждом из этих подпространств. [35]
В каждой ячейке машина может записывать символ из конечного алфавита А. Первоначально лента должна быть пустой, кроме конечного числа ячеек, заполненных заранее. Основная разница между машиной Тьюринга и конечным автоматом состоит в том, что: ( i) лента машины Тьюринга бесконечна; ( И) машина Тьюринга может двигаться вдоль ленты ( или смещать ленту) в любом направлении. Это придает машине бесконечную память, которой можно пользоваться в ходе вычислений. Сверх того, каждую ячейку мож но просматривать многократно. Формальное определение машины Тьюринга существует в нескольких вариантах. [36]
Эта работа касается определения нижних границ времени вычисления некоторых входно-выходных преобразований и взаимосвязи между временем вычисления и размерностью лент машины Тьюринга. Метод, использованный при установлении этой границы, применяется в разд. Этот результат обобщается в разд. Хартманиса - Стирнза [2, 3] не может быть значительно улучшен и что имеется существенная разница между размерностью и количеством лент машины Тьюринга. [37]
Страницы: 1 2 3