5.33. Постройте машины Тьюринга, которые вычисляют следующие функции:
а) f(x) = x + 1;
б) О (х) = 0.
Указание. См. задачи 5.1 и 5.14 для задач п. а) и б) соответственно.
5.34. Постройте, машины Тьюринга, вычисляющие следующие функции:
а) f (x1, х2, х3) = х2;
б) f (x1, х2, …, х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) = 21х.
|
|
Указание. а) См. задачу 5.4. д) См. задачу 5.24. е) См. задачу 5.23. и) См. задачу 5.6.
Решение. в) Читателю предлагается проверить, что данная функция вычисляется машиной Тьюринга со следующей функциональной схемой (программой): q10®q20П, q20 ® q00Л, q21 ® q31П, q31 ® q30П, q30 ® q40Л, q40 ®q40Л, q41 ® q00Л.
5.36. Докажите, что следующие функции вычислимы по Тьюрингу, построив соответствующие машины Тьюринга:
а)
б)
Указание. См. задачу 8.2.
5.37. Cоставьте программы машин Тьюринга, вычисляющих следующие функции:
а) е)
б) ж)
в) з)
г) и)
д) и)