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

f1(n) = номер программы: ' x:= 0; Пn ; y:= 0'.

f2(n) = номер программы: 'Пn ; y:= x'.

f3(n) = номер программы: ' x:= 0; Пn ; y:= 0; y:= y+1'.

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

• # Следующий конечный автомат - преобразователь MINUS= <ΣX ={0, 1} ΣY= { 0, 1}, Q ={ 0, 1, 2 }, 0, Φ, Ψ>, где [Большая Картинка] вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?
• # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a →​ 1, 0 b →​ 3, 1 a →​ 3 1 b →​ 2, 2 a →​ 3, 2 b →​ 2, 3 a →​ 3, 3b →​ 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 a →​ q0, q0 b →​ q1, q1 a →​ q1, q1 a →​ q2 Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B? С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, Φ1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, Φ2>, С3 = < {a,b}, {0, 1, 2, 3, q1, q2}, 0, F3={ q2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a →​ 1, 0 b →​ 3, 1 a →​ 2, 1 b →​ 1, 2 a →​ 1, 2 b →​ 3, 3 a →​ 3, 3b →​ 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 b →​ q0, q0 b →​ q1, q1 a →​ q1, q1 a →​ q2, q2 b →​ q0 Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B? С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2},Φ1> , С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2},Φ2> , С3 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F3={ q2}, Φ3> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением (00 + 1)*1? С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1> , С2 = < {0,1}, {q, p, r, s }, q, F2={ s}, Φ2> , С3 = < {0,1}, {q, p, r, s, t}, q, F3={ s}, Φ3> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x двоичный логарифм от x, т.е. функцию [ log2( x)]? [Большая Картинка]