Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Как продвинуть сайт на первые места?
    Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.
    Ускорение продвижения
    Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.
    Начать продвижение сайта
  • Задание 12.






    12.1. Показать, что следующие функции примитивно рекурсивны:

     

    а) f(x, у) = х + у

    Решение: возьмем в качестве функций g(x) и h(x, y, z) следующие простейшие всюду определенные функции: ,

    По схеме примитивной рекурсии f (x, 0) = g (x) = x

    f (x, y +1) = h (x, y, f (x, y)) = f (x, y)+1

    В частности, f (x, 1) = x +1, f (x, 2) = x +2 и т.д.

    Следовательно, f (x, y) = x + y

     

    б) f(x, у) = х × у

    Решение: возьмем в качестве функций g(x) и h(x, y, z) следующие всюду определенные примитивно рекурсивные функции: g (x) = 0(x), h(x, y, z) = (операция суммирования определена выше).

    По схеме примитивной рекурсии f (x, 0) = g (x) = 0, а

    f (x, y +1) = h (x, y, f (x, y)) = x + f (x, y)

    В частности, f (x, 1) = x, f (x, 2) = x+ x = 2 x f (x, 3) = 3 x

    Следовательно, f (x, y) = x × y

     

     

    в) f(x, у) = ху (00 = 1 – принимаем по определению)

    Решение: возьмем в качестве функций g(x) и h(x, y, z) следующие всюду определенные примитивно рекурсивные функции: g (x) = S(0(x)), h(x, y, z) = (операция умножения определена выше).

    Тогда f (x, 0) = 1 f (x, у+ 1) = х × f (x, y)

    f (x, 1) = x, f (x, 2) = x 2, f (x, 3) = x 3 и т.д.

    Следовательно, f (x, y) = ху

     

     

    г)

    Решение: возьмем в качестве функций g(x) и h(x, y) следующие всюду определенные примитивно рекурсивные функции: ,

    По схеме примитивной рекурсии

    f (0) = g(0)=0, f (x +1) = h (x, f (x))

    Тогда f (1) = h(0, f(0)) = 0+0(f (0)) = 0, f (2) = h (1, f (1))=1+0(f (1)) = 1, f (3) = 2+0 = 2

    и т.д.

    То есть, для

     

    д) f(x, у) =

    Решение: возьмем в качестве функций g(x) и h(x, y) следующие всюду определенные примитивно рекурсивные функции: для х> 0 = f (x, 0) = g (x) = = x

    Для x> y+1 = f (x, у+ 1) =

    В частности, = f (x, 1) = = x -1

    = f (x, 2) =

     

    е)

    Решение: по аналогии с предыдущим положим Sg (0) = 0(0), h (x, y) = S (0( (x, y))).

    Тогда, для x 0 Sg (x +1) =h(x, Sg(x)= S(0(x))

     

    ж)

    Решение: положим ,

    Тогда для x 0

    е)

    Решение: данная функция примитивно рекурсивная, так как может быть представлена как композиция примитивно рекурсивных функций построенных выше:

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.