Указатель на первой ленте указывает на первый символ слова x. Если через некоторое количество тактов машина приходит в состояние q



Скачать 136.59 Kb.

Дата05.04.2017
Размер136.59 Kb.
Просмотров50
Скачиваний0
ТипУказатель
Московский физико-технический институт
Факультет инноваций и высоких технологий
Сложность вычислений, осень Измерение времени работы на машинах Тьюринга
Детерминированной машиной Тьюринга с k лентами называется кортеж ?, ?, Q, q
1
,
q a
, q r
, ?
, где ?, ? и Q суть конечные непустые множества, причјм ? ? ? и ? ? Q = ?,
q
1
, q a
, q r
? и попарно различны, а ? : (Q \ {q a
, q r
}) Ч ?
k
? Q Ч Ч {L, N, R}
k
. ? называется входным алфавитом, ?  ленточным алфавитом, Q  множеством состояний, q и q r
 начальным, принимающими отвергающим состояниями соответственно, а функцией перехода. Среди элементов ? выделяют специальный символ # (бланк,
пробел, пустой символ, обозначается также как _, , ), не входящий в множество Машина состоит из k бесконечных в обе стороны лент, разделјнных на ячейки, и управляющего блока с указателями на каждую из k лент. За один такт машина считывает символы со всех k ячеек, на которые указывает, ив зависимости от внутреннего состояния и прочтјнных символов переходит в новое состояние, записывает новые символы и сдвигает каждый указатель влево или вправо или оставляет его на месте. Вначале работы на первой ленте написано слово x, все остальные ленты пусты, машина находится в состоятнии q
1
, а указатель на первой ленте указывает на первый символ слова x. Если через некоторое количество тактов машина приходит в состояние q a
, то говорят, что машина принимает слово x, если машина приходит в состояние q r
, то отвергает.
Машина распознајт язык L ? ?
?
, если она принимает все x ? L и отвергает все x ? L
1. Сформулируйте строго, что такое вычисление на машине Тьюринга (как последовательность конфигураций. Определите многоленточную машину Тьюринга, вычисляющая некоторую функцию изв Время работы машины на входе x считается как количество шагов машины на этом входе до прихода в завершающее состояние. Время работы машины в худшем случае считается как максимальное время работы на всех словах длины n. (Таким образом,
время работы в худшем случае есть функция от длины слова).
Пусть функции f и g отображают натуральные числа в натуральные ненулевые числа. Говорят, что) = O(g(n)), если ?C?N?n > Nf(n) < Cg(n);
€ f(n) = ?(g(n)), если ?c > 0?N?n > Nf(n) > cg(n);
€ f(n) = ?(g(n)), если ?c > 0?C?N?n > Ncg(n) < f(n) < Cg(n);
€ f(n) = o(g(n)), если ?c > 0?N?n > Nf(n) < cg(n);
€ f(n) = ?(g(n)), если ?C?N?n > Nf(n) > Cg(n).
3. Докажите, что f(n) = O(g(n)) эквивалентно ?C?nf(n) < Cg(n), а также анало- гичные факты для других асимптотик.
4. Докажите, что:
1
a) Если f(n) = o(g(n)) и g(n) = ?(h(n)), то f(n) + g(n) = ?(h(n));
b) Если f(n) = ?(h(n)) и g(n) = O(f(n)), то f(n) + g(n) = Функция T : N ? N называется конструируемой повремени, если T (n)
n и по унарной записи n можно вычислить двоичную запись T (n) за время O(T (n)).
5. Докажите, что функции n, n log n, n
2
, 2
n являются конструируемыми по времени.
Если T (n)  конструируемая повремени функция, то сложностным классом (называется множество всех языков, которые можно распознать машиной Тьюринга, работающей время O(T (n)). В дальнейшем все функции будем считать конструируемыми повремени, не оговаривая это особо.
Тезис Чјрча-Тьюринга в сильной форме гласит, что если некоторая функция вычисляется (некоторый язык распознајтся) на некотором физическом устройстве за время (n)
, то она вычисляется (он распознајтся) на машине Тьюринга за время O(T (для некоторого k. Следующие задачи являются иллюстрациями тезиса для вариаций определения машины Тьюринга.
6. Докажите, что если разрешить машине сдвигаться только налево и направо, ноне оставаться на месте, то время работы вырастет в постоянное число раз. Докажите, что если заменить ? на ??{#}, то время работы вырастет в постоянное число раз. Докажите, что если заменить ленты машины Тьюринга на бесконечные в одну сторону, то время работы вырастет в постоянное число раз. Докажите, что многоленточную машину Тьюринга с временем работы T (n) можно смоделировать на одноленточной машине со временем работы O(T (n)
2
)
. (Константа может зависеть от числа лент. Пусть каждая из лент машины Тьюринга представляет из себя клетчатую плоскость, по которой машина может сдвигать в любом из четырјх направлений. Докажите,
что язык, распознающийся на такой машине за T (n), лежит в DTIME((T (n))
2
)
11. Рассмотрим машину с произвольным доступом (random access). У такой машины в паре с каждой рабочей лентой есть адресная также есть специальное состояние q
access и два спецсимвола W ив ленточном алфавите. Если машина оказывается в состоянии q access в конфигурации bin(i)q на одной из адресных лент (bin(i) двоичная запись числа i), то символ ? записывается в ячейку с номером i на соответствующей рабочей ленте. Если машина оказывается в состоянии q access в конфигурации bin(i)q на адресной ленте, тов следующую за содержащей R ячейку записывается символ из ячейки с номером i на соответствующей рабочей ленте. Докажите, что язык,
распознаваемый на такой машине за T (n), лежит в DTIME((T (n))
2
)
12. Пусть есть слово x, записанное в обратном порядке. Докажите, что язык = {x ? {0, 1}
?
| x
R
= x}
, те. множество палиндромов, лежит в классе ноне распознајтся за время O(n) на одноленточной машине Тьюринга.
2


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал