Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

186 S j q r S k Q S m На пересечении i - го столбца и j – ой строки (i ≥ 0, j ≥ 0) записывается выражение q r S k Q, являющееся частью команды q i S j q r S k Q если такая команда есть . Если команды , начинающейся с q i S j , нет , то на пересечении i - го столбца и j – ой строки ставится прочерк . По заданной машине Тьюринга и начальной конфигурации К 0 найти заключительную конфигурацию для следующих вариантов . 1) q 0 q 1 0 q*1S q 0 0R 1 q 1 0R q 1 1L a) К 0 =1 2 q 0 1 3 01, б ) К 0 =1q 0 1 4 ; 2) q 0 q 1 q 2 0 q*0S q*1L q 0 1L 1 q 1 1R q 2 0R q 0 0R a) К 0 =1q 0 1 5 , б ) К 0 =q 0 1 3 01, в ) К 0 =10q 0 1 4 . 44. Доказать , что следующие функции примитивно рекурсивны : а ) sg(x)=    > = 0 х если 1, 0, х если , 0 ; б )