Математическая логика и теория алгоритмов

На пересечении г-го столбца и j-я строки (/>0,у>0) записывается выражение qrS^Q, являющееся частью команды qiSjqAQ, если такая команда есть, Если команды, начинающейся с qjSy, нет, то на пересечении ;-го столбца иу-й строки ставится прочерк. По заданной машине Тыоринга и начальной конфигурации Ко найти заключительную конфигурацию для следующих вариантов. 1 ) 0 q*lS qaOR 1 . qfiR ?ili a)ii:o=l>l'01. б)Л'о=1?о1^- 2) 9o 9i 92 0 cj*OS g*\L golL 1 q,\R q20R qoOR )Jfo=l^ol'; 6)Ko=qol'0\; в)Ко=Що1'. 43. Доказать, что следующие функции примитивно-рекурсивны: Г О, если д: = О, ^)sg(x)==\ (^1, еслид:>0; ^ _ fO, еслид:>0, б) sg{x) = j 1, еслил;=:0.