Вычислимые по Тьюрингу функции

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оставьте программы машин Тьюринга, вычисляющих следующие функции:     

а)                  е)            

б)                ж)      

в)                з)             

г)                и)      

д)               и)