Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.

(a) x := x+1, (b) x := 0, (c) x := y.

Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.

(a) x := x +1,

(b) пока x < y делай P все,

(c) пока x = y делай P все.

.

Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.

(a) если x < y то P1 иначе P2 конец,

(b) если x = y то P1 иначе P2 конец.,

(c) x := 0.

Пусть П₊ - это построенная в лекции программа, которая вычисляет функцию Ф₊(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x ее квадрат x · x ?

Пусть П₊ - это построенная в лекции программа, которая вычисляет функцию Ф₊(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x² +2x +2 ?

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x целую часть частного [ x/y] (пусть при y=0 результат равен 0)?

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x двоичный логарифм от x, т.е. функцию [ log₂( x)]?

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный корень из x, т.е. функцию [ x ^1/2]?

Пусть П₊ - это построенная в лекции программа, которая вычисляет функцию Ф₊(x,y) = x+y в переменной x, используя одну рабочую переменную z. Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x произведение x · y?

Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов ∧ и *, но головка "заблудилась" – она наблюдает символ ∧ и не знает левее или правее слова w находится. Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧^k w или w∧^k q ∧ (k > 0) переведут в конфигурацию q'w ?(В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l₁, r₁ , l₂ , r₂, l₃, r₃, l₄)

P1: q ∧ →​ l₁ * Л, l₁∧→​ r * П, l₁a→​ l₂a П, l₂ a→​ l₂ a Л, l₂ ∧→​ q'∧ П, r∧ →​ r ∧ П, r *→​ r₁ ∧ П, r₁ ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l₁ ∧ Л, r₁ a→​ r₂a Л, r₂ ∧→​ r₂∧ Л, r₂ *→​ r₃∧ П, r₃∧→​ r₃∧ П, r₃ a→​ q'a Н.

P2: q ∧ →​ l₁ * Л, l₁∧→​ r * П, l₁a→​ l₂a П, l₂ ∧→​ l₂∧ П, l₂ *→​ l₃∧ Л, l₃ ∧→​ l₃∧ Л, l₃ a→​ q'a Н,r∧ →​ r ∧ П, r *→​ r₁ ∧ П, r₁ ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l₁ ∧ Л,r₁ a→​ r₂a Л, r₂ ∧→​ r₂∧ Л, r₂ *→​ r₃∧ П, r₃∧→​ r₃∧ П, r₃ a→​ q'a Н.

P3: q ∧ →​ l₁ * Л, l₁∧→​ r * П, l₁a→​ l₂a П, l₂ ∧→​ l₂∧ П, l₂ *→​ l₃∧ Л, l₃ ∧→​ l₃∧ Л, l₃ a→​ l₄ a Л,l₄ a→​ l₄ a Л, l₄ ∧→​ q'∧ П, r∧ →​ r ∧ П, r *→​ r₁ ∧ П, r₁ ∧→​ l * Л, l ∧→​ l ∧ Л, l *→​ l₁ ∧ Л,r₁ a→​ r₂a Л, r₂ ∧→​ r₂∧ Л, r₂ *→​ r₃∧ П, r₃∧→​ r₃∧ П, r₃ a→​ q'a Н.

Пусть язык L в алфавите {a, b}, состоит из всех слов, которые заканчиваются на abb и содержат число символов b кратное 3, и пусть гоморфизм h: {0, 1,2}* →​ {a, b}* задан равенствами: h(0) = bab, h(1) = b, h(2) = ε Какие из следующих трех слов принадлежат прообразу h^-1(L) языка L при гомоморфизме h?W1 = 210102012, W2 = 201000201021, W3 = 021010212