Какими из следующих свойств обладает отношение алгоритмической сводимости A ≤m B ?

(а) рефлексивность: A ≤m A ,

(b) симметричность: A ≤m B ⇔ B ≤m A,

(с) транзитивность: A ≤m B и B ≤m C ⇐ A ≤m C .

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

• # В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M24, в котором q - начальное, а p – заключительное состояние. Какие из следующих программ могут быть использованы в качестве программы для M24 ? (В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |}) P1: q <a, b, c, |> →​ q <a, | , c, | > П , s <a, | , c, | > →​ s <a, | , c, | > Л , q <a, |, c, ∧> →​ q <a, ∧ , c, ∧> П , s <∧, ∧, ∧, ∧> →​ p <∧, ∧ , ∧, ∧> П. q <a, ∧, c, ∧> →​ s <a, ∧ , c, ∧> Л ,P2: q <a, |, c, d> →​ q <a, | , c, | > П , s <a, | , c, | > →​ s <a, | , c, | > Л , q <a, ∧, c, |> →​ q <a, ∧ , c, ∧> П , s <a, ∧, c, ∧> →​ p <a, ∧ , c, ∧> П. q <a, ∧, c, ∧> →​ s <a, ∧ , c, ∧> Л ,P3: q <a, b, c, |> →​ q <a, | , c, | > П , s <a, | , c, | > →​ s <a, | , c, | > Л , q <a, b, c, ∧> →​ s <a, ∧ , c, ∧> Л , s <a, ∧, c, ∧> →​ p <a, ∧ , c, ∧> П.
• # Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка. (a) x := x +1,(b) пока x < y делай P все,(c) пока x = y делай P все. .
• # Пусть задана логическая схема S=(V, E) : V= {a (X), b(Y), c(Z), d(V), e(¬), f(∨),g(∨),h(¬), i(¬), k(∨), m(∧) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, i), (b, f), (b, k), (c, g), (d, e), (e, g), (f, h), (g, k), (h, m), (i, f), (k, m) }. Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m? P1: P2: P3: X = ¬X; i = ¬X; X = ¬X; V = ¬V; e = ¬V; X = X ∨ Y; X = X ∨ Y; f = i ∨ Y; X = ¬X; Z = Z ∨ V; h = ¬i; V = ¬V; X = ¬X; g = Z ∨ e; V = Z ∨ V; Y = Y ∨ Z; k = Y ∨ g; V = Y ∨ V; Z = X ∧ Y. Z = h ∧ k. Z = X ∧ V.
• # Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,3 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
• # Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x целую часть частного [ x/y] (пусть при y=0 результат равен 0)? [Большая Картинка]