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

Вопрос

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

• только f1
• только f2
• только f3
• f1 и f2
• f1 и f3
• все

Ответ