Введение в схемы, автоматы и алгоритмы


Задачи - часть 2


F(x_1,...,x_n)= min\{y |\ f(x_1,...,x_n,y)=0\ \mbox{ или }\ g(x_1,...,x_n,y) > h(x_1,...,x_n,y) \}

является частично рекурсивной.

Задача 8.10. Докажите, что определенные выше функция нумерации n-ок cn(x1, … , xn) и обратные ей функции выбора i-го элемента набора cni(z) (1

i
n) являются примитивно рекурсивными.

Задача 8.11. Предположим, что все пары (x,y) натуральных чисел упорядочены по возрастанию суммы (x+y), а внутри группы пар с одинаковой суммой - по возрастанию x-координаты. Этот порядок выглядит так: (0,0), (0,1), (1,0),(0,2),(1,1), (2,0),… , (0,x+y), (1, x+y-1), … , (x,y), … , (x+y, 0), … . Пусть d(x,y) - это номер пары (x,y) в этом порядке (будем считать, что пара (0,0) имеет номер 0). Тогда функция d2 однозначно нумерует все пары.

  • Докажите, что
    d(x,y) = \frac{(x+y)(x+y+1)}{2} +x -1.
  • Найдите обратные функции d1(z) и d2(z) такие, что d1(d(x,y))=x, d2(d(x,y))= y и, следовательно, d(d1(z), d2(z))=z.




Начало  Назад  



Книжный магазин