В теореме 20.5 была доказана неразрешимость - Ответ на вопрос по любому предмету №1170990

Вопрос

В теореме 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 и f3
• только f2
• все
• f1 и f2
• только f1
• только f3

Ответ