Главная / Введение в схемы, автоматы и алгоритмы / В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые остан

В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе монотонности вычисляемой ею функции: M mon = {n | для любых x1 и x2, если x1 < x2, то ФПn,y (x1) < ФПn,y (x2)}. Какие из следующих функций сводят Mh0 к M mon ?
  • f1(n) = номер программы: 'xn:=x; x:= 0; Пn ; y:= xn'. (здесь переменная xn не входит в Пn )
  • f2(n) = номер программы: 'Пn ; y:= x'.
  • f3(n) = номер программы: 'y:= x; x:= 0; Пn ; y:= y+1'.
  • вопрос

    Правильный ответ:

    только f1
    только f2
    только f3
    f1 и f2
    f1 и f3
    все
    Сложность вопроса
    69
    Сложность курса: Введение в схемы, автоматы и алгоритмы
    92
    Оценить вопрос
    Очень сложно
    Сложно
    Средне
    Легко
    Очень легко
    Комментарии:
    Аноним
    Это очень простой решебник интуит.
    26 фев 2019
    Аноним
    Зачёт сдал. Лечу выпивать отмечать экзамен intuit
    17 окт 2017
    Оставить комментарий
    Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.