Способ композиции нормальных алгоритмов будет суперпозицией, если…

1. Выходное слово первого алгоритма является входным для второго

2. существует алгоритм С, преобразующий любое слово р, содержащееся i пересечении областей определения алгоритмов А и В

3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка

4. существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С{р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

Способ композиции нормальных алгоритмов будет объединением, если…

1. выходное слово первого алгоритма является входным для второго

2. Существует алгоритм с, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов а и в

3. алгоритм В будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) — A(p), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка

4. существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

Способ композиции нормальных алгоритмов будет разветвлением, если…

1. выходное слово первого алгоритма является входным для второго

2. существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В

3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D{p) - В{р), если С(р) = е, где е — пустая строка

4. существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С{р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

Способ композиции нормальных алгоритмов будет итерацией, если…

1. выходное слово первого алгоритма является входным для второго

2. существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В

3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В к С, а для любого слова р из этого пересечения D{p)= A(p), если С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка

4. существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

Сколько ячеек содержит лента машины Тьюринга?

1. 1024

2. бесконечное множество

3. 16

4. 4098

Укажите формат машины Тьюринга:

1. необходимо задать таблицу замены символов и определить адреса переходов для каждой команды

2. необходимо указать новый символ, микрооперацию лентопротяжного механизма машины и новое состояние

3. необходимо указать формулу для вычисления нового состояния машины

4. необходимо указать подстановки символов и условия перехода в новое состояние

Как может передвигаться каретка машины Тьюринга?

1. каретка может передвигаться вверх или вниз

2. каретка может передвигаться по диагонали

3. каретка может передвигаться вдоль ленты влево или вправо на одну ячейку

4. каретка не может передвигаться

Сколько лент имеет машина Тьюринга?

1. 4

2. 2

3. 1

4. 16

Какое максимальное количество адресов перехода можно задавать в команде машины Поста?

1. 3

2. 4

3. 2

4. 1

Нужно ли в каждой команде машины Поста указывать адрес отсылки?

1. нет, не нужно

2. не всегда

3. да, нужно

4. адрес проставляется автоматически самой машиной

Сколько символов используется для копирования команд машины Поста?

1. 4

2. 8

3. 6

4. 2

Сколько типов команд имеет машина Поста?

1. 6

2. 2

3. 4

4. 8

Укажите формат команды машины Поста:

1. указывается номер команды, код команды и один или два адреса отсылки

2. задается на сколько позиций надо переместить каретку и какой символ записать в ячейку

3. указывается алгоритм замены переменных

4. указывается формула вычисления результата команды

Тезис Черча-Тьюринга может быть сформулирован следующим образом:

1. для любой интуитивно вычислимой функции существует вычисляющая её значения машина Тьюринга

2. для некоторых интуитивно вычислимых функций существует вычисляющая её значение машина Тьюринга

3. машина Тьюринга существует для всех функций

4. машина Тьюринга не существует для всех функций

Какая из следующих простейших функций называется функцией-следованием?

1. O(x)=0

2. S(x)=x+1

3. I_mⁿ(x₁,x₂,...,x_n)=x_m, 1£m£n

4. C_qⁿ(x₁,x₂,...,x_n)=q, nÎN, qÎN

Какая из следующих простейших функций называется нуль-функцией?

1. O(x)=0

2. S(x)=x+1

3. I_mⁿ(x₁,x₂,...,x_n)=x_m, 1£m£n

4. C_qⁿ(x₁,x₂,...,x_n)=q, nÎN, qÎN

Какая из следующих простейших функций называется функцией проецирования (выбора)?

1. O(x)=0

2. S(x)=x+1

3. I_mⁿ(x₁,x₂,...,x_n)=x_m, 1£m£n

4. C_qⁿ(x₁,x₂,...,x_n)=q, nÎN, qÎN

Какая из следующих простейших функций называется функцией константой?

1. O(x)=0

2. S(x)=x+1

3. I_mⁿ(x₁,x₂,...,x_n)=x_m, 1£m£n

4. C_qⁿ(x₁,x₂,...,x_n)=q, nÎN, qÎN