Применение машин тьюринга к словам

К₂ = Б⁺ГВБ⁺ВГВБ⁺ВБ^Б^ВБ⁺.

а) машина не применима ни к какому непустому слову, т. е. применение машины к любому непустому слову при­водит к тому, что машина никогда не останавливается;

б) машина применима к любому непустому слову, т. е. любое непустое слово перерабатывается машиной в некоторое слово (в результате машина останавливается, т. е. приходит в состояние q₀);

в) машина применима только к словам вида , п  1;

г) машина применима только к словам вида, п  1, m  1.

Решение. а) Будем считать, что машина начинает работать из стандартного начального положения, т. е. в на­чальном состоянии q₁ «головкой» машины обозревается ячей­ка, в которой записана самая правая единица перерабатывае­мого слова. Тогда искомую машину построить нетрудно: из начального положения она должна неограниченно двигаться по ленте вправо. Вот ее функциональная схема:

А Q	q1	q2
a0	q0a0	q2a0П
1	q21П	q21П

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

ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ ФУНКЦИИ

5.33. Постройте машины Тьюринга, которые вычисляют следующие функции:

а) f(x) = x + 1;

б) О(х) = 0.

Указание. См. задачи 5.1 и 5.14 для задач п. а) и б) соответ­ственно.

5.34. Постройте, машины Тьюринга, вычисляющие следующие функции:

а) f (x₁, х₂, х₃) = х₂;

б) f (x₁, х₂, …, х_n) = х_m (1  m  n).

Указание. Попробуйте построить эти машины в виде компози­ции машин О, Б^, Б⁺, Ц, где О — машина из задачи 5.33, б, а Б^, Б⁺ и Ц - машины из задач 5.26, 5.27 и 5.30 соответственно.

5.35. Докажите, что следующие функции вычислимы по Тьюрингу, для чего постройте машины Тьюринга, вычисляю­щие их:

а) f (x, y) = х + y; ж) f (x, y) = НОД (х, y);

б) з)

в) и)  целая часть числа ;

г) к)

д) л) ;

е) f (x, y) = х  y; м) f (x) = 2х + 1; н) f (x) = 2^1х.
Указание. а) См. задачу 5.4. д) См. задачу 5.24. е) См. задачу 5.23. и) См. задачу 5.6.

Решение. в) Читателю предлагается проверить, что данная функция вычисляется машиной Тьюринга со следую­щей функциональной схемой (программой): q₁0q₂0П, q₂0  q₀0Л, q₂1  q₃1П, q₃1  q₃0П, q₃0  q₄0Л, q₄0 q₄0Л, q₄1  q₀0Л.

5.36. Докажите, что следующие функции вычислимы по Тьюрингу, построив соответствующие машины Тьюринга:

а)

б)

Указание. См. задачу 8.2.

5.37. Cоставьте программы машин Тьюринга, вычисляющих следующие функции:

а) е)

б) ж)

в) з)

г) и)

д) и)

жүктеу/скачать 344.5 Kb.

Достарыңызбен бөлісу: