Постройте минимальные УБДР для функции f(x1, x2, x3, x4)= (x1 ∧ x2) +( x3 ∧ x4) относительно двух упорядочений переменных:

a) x1 < x2 < x3 < x4 и

b) x1 < x3 < x2 < x4.

Определите сложности этих двух схем.

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

• # В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ≤ i, j ≤ m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M43, в котором q - начальное, а p – заключительное состояние. Какие из следующих программ могут быть использованы в качестве программы для M43 ? (В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |}) P1: q <a, b, |, d > →​ q < a, b , |, | > П , s < a, ,b | , | > →​ s < a, b, | , | > Л , q < ∧, b, ∧, d> →​ s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> →​ p < ∧, ∧, ∧, ∧> П ,P2: : q <a, b, c, | > →​ q < a, b , c, | > П , s < a , b, |, d > →​ s < a , b, |, | > Л , q <a, b, |, d > →​ q < a, b, |, d > П , s < ∧, ∧, ∧, ∧> →​ p < ∧, ∧, ∧, ∧> П. q <a, b, ∧, ∧> →​ s < a , b, ∧, ∧ > Л , s < a , b, ∧, | > →​ s < a , b, ∧, ∧ > Л,P3: : q <a, b, |, d > →​ q < a, b , |, | > П , s < a, ,b | , | > →​ s < a, b, | , | > Л , q <a, b, ∧, | > →​ q < a, b, ∧, ∧ > П , s < ∧, ∧, ∧, ∧> →​ p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> →​ s < ∧ , b, ∧, d > Л ,
• # Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка. (a) x := x+1, (b) x := 0, (c) x := y.
• # Пусть задана УБДР D=(V,E): V={v1 (x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0), (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 1), (v8, 1; 0)} ( для каждого ребра третий параметр после ; - его метка 0 или 1). Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.
• # Пусть структурированная программа P: x:= y+1; v:= u+1; пока x < v делай если y < x то y := y+1 иначе x := x +1; u := u+1 конец все начинает работу в состоянии σ : σ(x) = 2, σ(y) =3, σ(u) = 5, σ(v) =0В каком из следующих состояний σ1она завершит свою работу?
• # Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф: \begin{array}{lll} q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л & r\ 0 \rightarrow r\ 0\ Л q\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л & r\ 1 \rightarrow r\ 1\ Л q \wedge \rightarrow p\ \wedge Л & p \wedge \rightarrow ! \wedge П & r \wedge \rightarrow ! \wedge П \end{array} В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?