Многоленточная машина тьюринга примеры

Машина Тьюринга

Содержание

Машина Тьюринга (англ. Turing machine) — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:

При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.

Определение [ править ]

Определение машины [ править ]

Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.

Определение процесса работы [ править ]

Особо следует рассмотреть случай переходов по пробельному символу:

Для машины Тьюринга, которая пишет символ [math]B[/math] на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

Результат работы [ править ]

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

Примеры машин Тьюринга [ править ]

Прибавление единицы [ править ]

Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:

Проверка того, является ли слово палиндромом [ править ]

Варианты машины Тьюринга [ править ]

В этом разделе приведены различные варианты машин Тьюринга, которые не отличаются от обычных машин Тьюринга по вычислительной мощности.

Многодорожечная машина Тьюринга [ править ]

Машина Тьюринга с полубесконечной лентой [ править ]

Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой.

Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с бесконечной лентой следующим образом:

Затем перенумеруем ячейки, и запишем символ [math]c \in \Pi \setminus \Sigma, B[/math] в начало ленты, который будет означать границу рабочей зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.[math]\triangleleft[/math]

Многоленточная машина Тьюринга [ править ]

Многоленточная машина с [math]n[/math] дорожками эмулируется многодорожечной машиной с [math]2n[/math] дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом [math]*[/math] позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов [math]*[/math] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:

Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

Универсальная машина Тьюринга [ править ]

Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, универсальный язык перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.

Источник

Модификации машин Тьюринга

5. Модификации машин Тьюринга

5.1. Многоленточные машины Тьюринга и их преобразование в одноленточные.

Для некоторых задач составление алгоритмов работы обычной машины Тьюринга представляет значительные трудности, связанные с необходимостью где-то хранить результаты промежуточных вычислений, или производить посимвольное сравнение нескольких групп элементов. В некоторых случаях наличие дополнительной (рабочей) ленты или размещение входных слов на нескольких лентах одновременно позволяет получить более лаконичное решение.

Однако как это ни покажется парадоксальным, вычислительная способность таких машин совершенно не превосходит их одноленточные аналоги. Иными словами, задачи, которые можно решить на многоленточной машине с произвольным количеством лент, всегда решаются и при помощи одноленточной машины.

Основные свойства многоленточных машин

Многоленточная машина для каждой ленты может иметь свой алфавит. Ленты в машине движутся независимо друг от друга. Однако состояние для всех лент машины единое, по сути это состояние управляющего механизма. Собственно ранее, при рассмотрении одноленточных машин, было принято считать что лента неподвижна, а головка перемещается в заданном направлении. Но для рассмотрения многоленточным машин это не вполне удобно, потому что ленты являются независимыми, а наглядно представить перемещение единого управляющего механизма по разным направлениям весьма проблематично. Итак, считаем что управляющий механизм неподвижен, а ленты могут свободно перемещаться вправо, влево или оставаться на месте независимо друг от друга.

Программа многоленточной машины

Как и ранее, способ записи программ для многоленточных машин – дело вкуса и договоренностей. Далее в тексте будет использоваться следующий порядок записи

Преобразование многоленточных машин в одноленточные

Пусть есть К-ленточная машина М и одноленточная машина М*. Считаем что лента машины М* разбита на 2К дорожек. Нечетные полоски отображают ленты машины М, а четные – положение машины М на своих лентах, т. е. например на 2-ой ленте специальный символ Х стоит в той клетке, которая находится непосредственно под клеткой, обозреваемой управляющей головкой на первой ленте. Одна клетка машины М* равна целому столбцу в таблице. Положим что в начале процесса моделирования М* воспринимает самую левую метку положения. Затем М* будет двигаться вправо, считая метки положений путем смены внутренних состояний и запоминая соответствующие значения на нечетных дорожках.

5.2. Универсальные машины.

Тьюринг показал возможность построения определённой вычислительной машины U, универсальной в том смысле, что на U можно выполнить любое вычисление.

Универсальность некоторой машины Тьюринга выражается в её способности путём подходящего кодирования выполнить любое вычисление, которое могла бы выполнить любая заданная машина Тьюринга. Однако к этому, несомненно, надо присоеденить то условие, что кодирование должно быть в некотором смысле простым. В самом деле, нет особой выгоды считать универсальной машину Тьюринга, у которой кодирование, по существу, требует работы другой универсальной машины. Отсюда возникает задача явного определения универсальной машины Тьюринга.

Кодирование программы машины Тьюринга.

На ленте УМТ записывается кодовый номер (программа произвольной МТ и входное слово) данной МТ, и эта машина (УМТ) должна читать этот кодовый номер и выполнять всю работу той машины, программа которой записана на её ленте. УМТ должна печатать знаки в таком же коде, как и в таблице. Соответственно для такой машины необходимы входные слова, записанные по какому-то методу (единообразный метод записи программ и входных слов). Поскольку число возможных знаков – бесконечно много, а у машины конечный алфавит, поэтому всё (и состояния, и символы) кодируется последовательностью других знаков (чисел).

Ai = 1…1 (A1=1, A2=11, A3=111 и т. д.)

Sj = 2…2 (S1=2, S2=22, S3=222 и т. д.)

В этом случае всю программу работы машины можно записать неким числом, причем возможны два варианта записи:

1. Без разделителя команд. В этом случае команды следует писать в формате Aold Sold Anew R Snew, тогда две команды, записанные непосредственно друг за другом, будут явно различаться элементарным анализатором.

2. С разделителем команд, допустим Х, которые можно закодировать числом 4.

Возьмем в качестве примера машину Тьюринга, которая на пустой ленте бесконечно много раз печатает последовательность 001. Программа такой машины выглядит следующим образом (λ-пустой знак)

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

Тогда запись программы машины будет выглядеть так:

код данной машины (запись без разделителя команд)

222 код данной машины (запись с разделителем команд)

λ A 0 R B λ B 0 R C λ C 1 R A – соответствующие команды

Т. о. каждая МТ представлена числом – это декриптивное (описательное) число машины. Вместе с тем оно является кодом для входного слова.

Построение универсальной машины Тьюринга

По сути УМТ является программируемой машиной Тьюринга, т. е. собственно программа не является внутренним элементов функциональной схемы, которая управляет считывающей головкой, а просто записана на ленте. Т. о. одна и та же машина получает способность выполнять любую задачу.

Рассмотрим УМТ. Ее алфавит ограничен символами 1,2,3,4. Тогда лента выглядит следующим образом (цифру 5 используем для разделения описания машины и описания входного слова)

dW – описание входного слова, в котором каждый символ слова Ai записан в виде наборов по несколько 1, разделенных специальным символом 4 (разделитель).

Описание машины – слово, разбитое на команды. УМТ читает описание данной машины, а затем перерабатывает входное слово так, как бы это сделала МТ. УМТ имеет такой же алфавит, как и у предъявленной ей машины. Отсюда вытекает необходимость наличия меток для указания положения исходной МТ. Такие метки удобно ставить вместо разделителя, стоящего непосредственно перед группой ячеек, содержащих код рассматриваемого символа. Поскольку первые 5 цифр алфавита заняты под кодирование программы МТ, будет заменять разделитель перед символом, на котором остановилась исходная МТ, на цифру 6.

Составление таблицы для одноленточной УМТ довольно сложное дело. Поэтому для наглядности построим трехленточную машину, которую всегда можно преобразовать в одноленточную по рассмотренному в предыдущей главе принципу.

Ленты трехленточной универсальной машины Тьюринга

Исходная лента, на которой записан код таблицы исходной МТ

Рабочая лента, на ней записываются внутренние состояния исходной МТ

Выходная лента – закодированная лента исходной МТ.

Вначале моделирования каждого такта работы исходной МТ, УМТ занимает на 3-ей ленте первую клетку кодовой ячейки. Эта клетка соответствует той клетке на ленте исходной МТ, которую в данный момент воспринимает считывающая головка исходной МТ.

УМТ движется по входной ленте, пока не дойдёт до команды, в которой внутреннее состояние совпадает с записью на 2-ой ленте, а воспринимаемый символ – с тем, который записан на входной ленте, в кодовой ячейке которой изображено положение исходной машины. Сравнение происходит по разрядам. В итоге УМТ находит на входной ленте нужную для исполнения команду МТ. УМТ считывает инструкцию, соответствующую этой команде.

Эта инструкция выполняется, а именно:

изменяется положение исходной МТ. Например, если инструкция гласит «шаг вправо», то на 3-ей ленте делается необходимое количество шагов вправо до ближайшего нового разделителя команд, который заменяется меткой текущего положения (вместо 4 ставится символ 6). изменяется внутреннее состояние исходной МТ. На второй ленте вместо старого записывается ее новое состояние. изменяется символ, содержащийся в рассматриваемой ячейке. Поскольку разные символы кодируются различным количеством единичек, то в случае замены символа необходимо предусмотреть процедуру сдвига (растягивание или сжимание слова на нужное число клеток)

После этого моделируется следующий такт работы исходной МТ. Для этого снова анализируется содержание второй ленты (это теперь текущее состояние МТ) и символ, записанный справа от указателя текущего положения управляющей головки (специальная метка 6).

Эту УМТ можно существенно упростить с помощью 2-ой теоремы Шеннона (преобразовать в УМТ с двумя символами), следовательно, достаточно построить УМТ для МТ, имея два знака в алфавите. В результате на третьей ленте чего не нужно ничего сдвигать.

Источник

ГЛАВА 1. Машина Тьюринга как вычислительная модель

Дата добавления: 2015-01-16 ; просмотров: 4254 ; Нарушение авторских прав

В логике с помощью понятия машины Тьюринга строится теория неразрешимых проблем, однако в вычислительной практике чаще приходится иметь дело с разрешимыми, но “трудно решаемыми” проблемами. Выбирая и здесь в качестве вычислительной модели машину Тьюринга, мы руководствуемся тем, что она проста и допускает те же языки, что и компьютер, причем сложность вычислений на машине Тьюринга полиномиальна от числа шагов компьютера.

X – внешний алфавит символов (букв на ленте), включающий символ L;

Q – конечный алфавит внутренних состояний;

q₀ – инициальное состояние (начало работы), q₀ Î Q;

F– множество заключительных состояний, FÌ Q;

Переходы осуществляются на основе текущего состояния и обозреваемого считывающей головкой символа к следующему состоянию, переписыванию символа и сдвигу головки (вправо R, влево L, на месте S).

Можно определить функцию переходов

В случае однозначной функции d машина Тьюринга называется детерминированной машиной Тьюринга.

Текущей конфигурацией машины Тьюринга называют цепочку значащих (отличных от L) символов, записанных на ленте в данный момент времени, вместе с символом состояния, помещенным в цепочку перед обозреваемым символом.

Останов (завершение работы) происходит в заключительном состоянии или когда левая часть (до ®) ни одной из машинных команд не содержится в полученной конфигурации. Говорят, что машина допускает вход, если она останавливается на нем в заключительном состоянии.

q₀0 ® LRq₁ Состояния Символ

q₁0 ® 0Rq₁ 0 1 L

q₄0 ® 0Lq₄ где функция переходов задается таблицей

Язык L допускается (распознается) за полиномиальное время, если существует машина M, которая допускает (распознает) язык L, причем всякое слово wÎ L допускается (распознается) за время O(n k ), где n – длина слова w, а k – не зависящее от w число.

Теорема. Класс P есть множество языков, допускаемых за полиномиальное время.

Многоленточная машина Тьюринга.

Для имитации работы компьютера используются многоленточные машины Тьюринга. В начальной конфигурации многоленточной машины на первой ленте размещается вход (конечная последовательность символов, куда не входит L), все клетки остальных лент содержат символ L, считывающие головки всех лент находятся в начальном состоянии.

За один переход осуществляются следующие действия:

— управление переходит в новое состояние,

— на каждой ленте записывается новый (или тот же) символ;

— считывающие головки каждой из лент независимо сдвигаются на одну ячейку (R,L,S).

Теорема.Каждый язык L, допускаемый многоленточной машиной Тьюринга, рекурсивно перечислим.

Теорема.Время, необходимое одноленточной машине N для имитации n переходов k-ленточной машины M, есть O(n 2 ).

Доказательство. После n переходов машины M маркеры головок разделены не более, чем 2n клетками, так что и машине N надо сдвинуться не более, чем на 2n клеток вправо, чтобы найти все маркеры головок. Теперь ей надо совершить проход влево, изменяя содержимое M лент и сдвигая головочные маркеры, что потребует не более 2n сдвигов влево плюс не более 2k переходов для изменения направления движения и записи маркера в клетку. Таким образом, число переходов N для имитации одного из переходов машины M не более 4n+2k, т.е. O(n). Для n переходов требуется времени в n раз больше, т.е. O(n 2 ). “

Недетерминированные машины Тьюринга.

По причинам, которые вскоре будут понятны, недетерминированные машины Тьюринга являются ключевым понятием в теории NP-полных задач. Недетерминированная машина Тьюринга отличается от обычной (детерминированной) машины Тьюринга тем, что может иметь более одного перехода от текущей конфигурации к следующей. Недетерминированная машина допускает слово w, если существует хотя бы одна цепочка конфигураций, ведущая от начальной конфигурации в заключительную. Существование других последовательностей конфигураций, не ведущих в заключительное (допускающее) состояние не имеет значение. Работу недетерминированной машины на входе w можно представить в виде дерева, где каждый путь из корня w в лист представляет некоторую последовательность возможных шагов машины. Если s_w кратчайшая последовательность возможных шагов работы машины, которая оканчивается допускающей конфигурацией, то ½s_w½ есть время, затраченное машиной на обработку входа w. Если на входе w никакая последовательность не приводит к допускающей конфигурации, то время, затраченное на обработку w не определено. Считается, что недетерминированная машина Тьюринга на входе w параллельно выполняет все возможные последовательности шагов, пока не достигнет допускающего состояния или окажется, что ее программа не применима к полученной конфигурации.

Остается открытым вопрос, существуют ли языки, допускаемые недетерминированной машиной Тьюринга с данной временной и емкостной сложностью и не допускаемые никакой детерминированной машиной с той же сложностью.

Недетерминированные машины Тьюринга допускают те же языки, что и детерминированные. Однако, надо заметить, что последним приходится за это расплачиваться сильным увеличением временной сложности.

Обозначим через L(M) множество всех слов wÎX*, допускаемых машиной M, L(M) называют языком машины M.

— Машина M ’ проверяет состояние и обозреваемый символ и, если состояние допускающее, также переходит в допускающее состояние.

— Если состояние не допускающее и из данной конфигурации есть k переходов, то M ’ использует вторую ленту для создания k копий, которые записываются в конце очереди на ленте 1.

— M ’ изменяет k конфигураций в соответствии с программой машины M.

— M ’ перемещает отметку текущей конфигурации на следующую справа и цикл повторяется с шага 1.

Допустим, что m есть максимальное число выборов машины M в любой конфигурации. Тогда существует одно начальное состояние M, не более m конфигураций, достижимых за 1 шаг, не более m 2 конфигураций, достижимых за 2 шага и т.д. Таким образом, после n переходов машина M может достичь не более 1+ m +m 2 +…+m n £ n×m n конфигураций. Порядок, в котором машина M ’ исследует конфигурации, называется “поиском в ширину”, т.е. M ’ исследует все достижимые конфигурации машины M за 0 шагов, достижимые за 1 шаг и т.д.

Допускающая конфигурация машины M будет рассмотрена машиной M ’ в числе первых n×m n конфигураций. Таким образом, если машина M допускает, то машина M ’ также допускает, т.е. L(M) = L(M ’ ). “

Теорема. Если M недетерминированная машина Тьюринга с емкостной сложностью S(n), то найдется детерминированная машина Тьюринга M ’ с емкостной сложностью O(S 2 (n)) и L(M ’ ) = L(M).

Теорема. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга M = (X, Q, q₀, F, I) с временной сложностью T(n), то он допускается одноленточной недетерминированной машиной с временной сложностью O(T 2 (n)).

Доказательство. Пусть M₁ одноленточная недетерминированная машина Тьюринга, имеющая на ленте 2k дорожек, т.е. ленточные символы машины M₁ представляются 2k-членными кортежами, в которых на нечетных местах стоят символы алфавита X, а на четных – либо символ L, либо маркер #. Дорожки с нечетными номерами соответствуют k лентам машины M, а каждая дорожка с четным номером 2j содержит символ L во всех ячейках, кроме одной, где стоит маркер #, отмечающий положение головки машины M на ленте j, которой соответствует дорожка 2j-1. Машина M₁ моделирует один шаг работы машины M следующим образом. Допустим, что вначале головка машины M₁ обозревает клетку, содержащую самую левую головку машины M.

— Головка машины M₁ движется вправо, пока не минует все k маркеров положений головок на дорожках с четными номерами. При этом M₁ запоминает в своем состоянии символы, обозреваемые каждой из головок машины M. Теперь M₁ делает недетерминированное развлетвление, исходя из состояния машины M, которое машина M₁ запомнила в своем состоянии, и обозреваемых машиной M на лентах символов, которые машина M₁ также нашла.

— Выбрав для моделирования шаг машины M, машина M₁ изменяет в соответствии с ним состояние машины M, которое она помнит в своем состоянии. Затем M₁ сдвигает свою головку влево и проходит все маркеры, изменяя ленточный символ на дорожке над маркером и сдвигая маркер не более чем на одну клетку (L,R,S).

Машина M₁ промоделировала один шаг работы машмны M. Действия машины M₁ на этом шаге детерминированы. Ее головка находится правее левого маркера не более чем на две ячейки. Начиная с этого маркера цикл можно повторить.

Если машина M допускает цепочку w длины n, то совершает при этом не более T(n) переходов. Очевидно, что в последовательности из T(n) шагов головки мащины M могут разойтись не более чем на T(n) клеток, и, значит, M₁ может смоделировать один шаг этой последовательности не более чем за O(T(n)) своих шагов. Таким образом, M₁ допускает цепочку w, выполняя не более чем O(T 2 (n)) переходов. Отсюда следует, что M₁ допускает язык L и имеет временную сложность O(T 2 (n)). “

Следствие 1. Если язык допускается k-ленточной детерминированной машиной Тьюринга с временной сложностью T(n), то он допускается одноленточной детерминированной машиной Тьюринга с временной сложностью O(T 2 (n)). “

Следствие 2. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n). “

Следствие 3. Если язык допускается k-ленточной детерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной детерминированной машиной Тьюринга с емкостной сложностью S(n). “

Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга.

К основным компонентам вычислительной машины относятся оперативная память и процессор. Программы и данные, представленные в двоичном алфавите, помещаются в память. При выполнении программы отдельные ее команды и нужные данные извлекаются из памяти в процессор и наоборот – значения, получаемые при выполнении команд, записываются в ячейки памяти.

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

Процессор состоит из устройства управления (УУ) и арифметического устройство (АУ). Устройство управления содержит счетчик тактов, команд и т.д., вырабатывает управляющие сигналы для выполнения команд, передачи данных и т.д. Процессор содержит регистры операндов, линии связи и линии задержки для непосредственной реализации процессов вычислений.

Наряду с процессором и памятью компьютеру необходимы еще устройства ввода/вывода.

Для имитации компьютера на машине Тьюринга существенны две вещи:

— существуют ли инструкции, выполняемые компьютером, и недоступные для машины Тьюринга;

— работает ли компьютер быстрее машины Тьюринга, т.е. более, чем полиномиальная зависимость разделяет время работы компьютера и машины Тьюринга при решении какой-то проблемы.

Неформальная модель реального компьютера:

— память, состоящая из последовательности слов и их адресов. В качестве адресов будут использоваться натуральные числа 0,1, …;

— программа компьютера, записанная в слова памяти, каждое из которых представляет простую инструкцию. Допускается “непрямая адресация” по указателям;

— каждая инструкция использует конечное число слов и изменяет значение не более одного слова;

— имеются слова памяти с быстрым доступом (регистры), но скорость доступа к различным словам влияет лишь на константный сомножитель, что не искажает полиномиальную зависимость.

Возможная конструкция машины Тьюринга для имитации компьютера

представлена на рис.

Функционирование такой имитирующей машины:

1.Найдя на 1-й ленте адрес, совпадающий с номером инструкции на 2-й ленте, исследуем значение по нему и копируем на 3-ю ленту. Первые биты инструкции задают действие (копировать, вставить, ветвиться и т.д.), оставщиеся биты – адрес или адреса, используемые в этом действии.

2. Если в инструкции содержится значение по некоторому адресу, то этот адрес копируется на 3-ю ленту, а позиция инструкции на 2-ю дорожку 1-й ленты.

3. Далее инструкция выполняется. С новым значением можно сделать следующее:

a) скопировать по другому адресу;

Второй адрес извлекается из инструкции, помещается на 3-ю ленту, находится на 1-й ленте и значение по нему копируется в зарезервированное для него пространство. Если для нового значения надо больше (меньше) памяти, чем для старого, пространство изменяется путем сдвига, а именно,

(1) на рабочую ленту копируется часть ленты справа от того места, куда надо поместить новое значение;

(2) новое значение записывается на 1-ю ленту;

(3) рабочая часть копируется обратно на 1-ю ленту справа от нового значения.

b) прибавить найденное значение по другому адресу;

Ищем второй адрес на первой ленте, выполняем сложение значения по этому адресу и записанному на 3-й ленте.

c) перейти к выполнению инструкции по адресу, записанному на 3-й ленте, для чего лента 3 копируется на ленту 2, и цикл инструкций начинается снова.

4. Выполнив инструкцию (не являющуюся переходом), прибавляем 1 к счетчику на ленте 2 и вновь начинаем цикл инструкции.

Теперь надо убедиться, что если проблему можно решить за полиномиальное время на компьютере, то ее можно решить за полиномиальное время на машине Тьюринга и наоборот. Как следует из доказанных выше теорем, достаточно использовать многоленточную машину Тьюринга, так как различие во времени работы одноленточной и многоленточной машин Тьюринга полиномиально.

Время работы машины Тьюринга, имитирующей компьютер

Введем следующие ограничения на модель компьютера:

— Ни одна компьютерная инструкция не должна порождать слово, длиннее, чем на 1 бит, своих операндов.

— Инструкция, применяемая к словам длины m должна выполняться не более, чем за 0(m 2 ) шагов на многоленточной машине Тьюринга.

Назовем такие операции допустимыми.

Этим условиям удовлетворяют сложение, сдвиг на 1 бит, сравнение значений, которые выполняются на многоленточной машине Тьюринга за 0(m) шагов. А также умножение m-битовых целых, если его имитировать с помощью m последовательных сложений со сдвигами на 1 бит влево. Время выполнения операции умножения будет пропорционально квадрату длины сомножителей. .

Теорема.Для компьютера, обладающего указанными свойствами, описанная выше модель машины Тьюринга может имитировать m шагов компьютера не более, чем за 0(m 3 )шагов.

После выполнения n шагов компьютер не может породить слово, длиннее c+n, и не может создать или использовать адрес, занимающий больше c+n битов. Каждая инструкция порождает не более одного нового адреса, получающего значение, поэтому после выполнения n инструкций имеем d+n адресов. Каждый адрес-значение занимает не более 2(c+n) +2 разрядов, а после выполнения n инструкций не больше 2(d+n)(c+n+1), или 0(n 2 )

Для просмотра адресов одной инструкции компьютера требуется времени 0(n 2 ), слова имеют длину 0(n), а инструкции выполняются машиной Тьюринга за время 0(n 2 ), сдвиг для создания пространства для нового слова включает копирование данных объемом 0(n 2 ) с ленты 1 на рабочую ленту и обратно. Таким образом, машина Тьюринга имитирует один шаг компьютера за 0(n 2 ) своих шагов, а n шагов можно проимитировать за 0(n 3 ) шагов машины Тьюринга. “

Теорема.Выполнение n шагов работы компьютера можно проимитировать на одноленточной машине Тьюринга не более чем за 0(n 6 ) шагов.

Таким образом, машина Тьюринга может имитировать память и управление реального компьютера, используя только одну ленту для записи всех элементов памяти и их содержимого – регистров, основной памяти, дисков и других запомиинающих устройств. Отсюда можно быть уверенным, что все, не выполнимое машиной Тьюринга, не может быть вычислено и компьютером. “

Источник

• ← Как проверить мультиметром питание в проводке автомобиля
• Посчитать трейд ин авто с пробегом →