Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 12 стр.

   Предикат P(x, y, z) = y z+1 > x.
   Вычислим значение функции при x = 8, y = 2.
   При z = 0: P(8, 2, 0) = 1 > 8 - "ложь",
       z = 1: P(8, 2, 1) = 2 > 8 - "ложь",
       z = 2: P(8, 2, 2) = 8 > 8 - "ложь",
       z = 3: P(8, 2, 3) = 16 > 8 - "истина".
   Следовательно, [log y x ] = 3.


   2.6. Задания для самостоятельной работы
      Доказать примитивную рекурсивность следующих функций.
   1. Усеченное вычитание
                                          x − x 2 , если x 1 > x 2 ,
                               x1 ÷ x 2 =  1
                                          0,        если x 1 < x 2 .
   2. Функция знака
                                               0, если x = 0,
                                    Sg ( x ) = 
                                               1, если x ≠ 0.
   3. Нахождение минимального значения из двух заданных чисел f(x, y) = min(x, y).
   4. Нахождение максимального значения из двух заданных чисел f(x, y) = max(x, y).
   5. Усеченное вычитание
                                          x − 1, если x > 1,
                                  x ÷1 = 
                                         0,       если x < 1.
    6. Функция r(x, y) - остаток от деления y на x.
    7. Функция q(x, y) - частное от деления y на x.
    8. Доказать, что предикат Pdn(x) "x делится на n" примитивно-рекурсивен для любого n.
    9. Доказать, что предикат Pdn,m(x) "x делится на n и m" примитивно-рекурсивен для
любых n и m.
    10. Доказать, что отношение x1 > x2 примитивно-рекурсивно.
    11. Доказать, что предикат f(x) = g(x) примитивно-рекурсивен, если функции f(x) и g(x)
примитивно-рекурсивны.
    12. Дано множество слов одинаковой длины, причем первые два слова выделены.
Построить цепь от первого выделенного слова ко второму так, чтобы все слова этой цепи
были только из заданного множества. Соседние слова построенной цепи должны отличаться
только одной буквой.
    13. Дано множество слов. Построить из них кроссворд заданной конфигурации (число
слов может быть больше требуемого количества для заполнения кроссворда).
    14. Грани кубика разбиты на клетки 5х5. Каждая из клеток выкрашена в белый или
синий цвет. Переход из клетки в клетку допускается только через общую сторону при
условии совпадения цветов этих клеток. Построить маршрут перехода из одной заданной
клетки в другую заданную клетку этого же цвета.
    15. Имеется клетчатая ткань размером NxN клеток. Разрезать ее на M квадратных частей,
не нарушая целостности клеток.


                                 3. МАШИНЫ ТЬЮРИНГА


      3.1. Общие сведения
    Одним из первых формальных определений алгоритма было определение английского
математика А. Тьюринга, который в 1936 г. описал схему некоторой гипотетической