В машине Поста останов будет результативным …

1. при выполнении недопустимой команды

2. если машина не останавливается никогда

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

4. По команде «Стоп»

В машине Поста некорректным алгоритм будет в следующем случае:

1. при выполнении недопустимой команды

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

3. Машина не останавливается никогда

4. по команде «Стоп»

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

1. А = {а₄₀ О, Ь_А0 1, с₄₀ 2, ..., w₄₀ ?}

2. Л = {а₄₀ 0, а₄₀ 1, а₄₀ 2, ..., а₄₀ ?}

3. Л = {а₄₀ 0, а₄₁ 0, о₄₂ 0, ..., а₄₁ 0}

4. Л = {а,₀ 0, а₂₀ 0, о₃о 0, ■•■, «ад 0}

В машине Тьюринга состояниями являются:

1. {a₄₀ 0, a₄₀ 1,a₄₀2, …,a₄₀ t}

2. {q₄₁, q₄₂, q₄₃, …, q_4s}

3. {q₄₁, q₄₂, q₄₃, …, q_4s, a₄₀ 0, a₄₀ 1, a₄₀ 2,…,a₄₀ t}

4. {q₄₀, q₄₁, q₄₂, …, q_4s}

В машине Тьюринга предписание L для лентопротяжного механизма означает:

1. переместить ленту вправо

2. переместить ленту влево

3. остановить машину

4. занести в ячейку символ

В машине Тьюринга предписание R для лентопротяжного механизма означает:

1. переместить ленту вправо

2. переместить ленту влево

3. остановить машину

4. занести в ячейку символ

В машине Тьюринга предписание S для лентопротяжного механизма означает:

1. переместить ленту вправо

2. переместить ленту влево

3. остановить машину

4. занести в ячейку символ

В алгоритме Маркова ассоциативным исчислением называется…

1. совокупность всех слов в данном алфавите

2. совокупность всех допустимых систем подстановок

3. совокупность всех слов в данном алфавите вместе с допустимой системой подстановок

4. совокупность слов в алфавите, являющихся смежными

В ассоциативном счислении два слова называются смежными…

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

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

3. когда существует цепочка от одного слова к другому и обратно

4. когда они дедуктивны

В алгоритме Маркова дана цепочка Р Р₁, Р₂ ... Р_к. Если слова P₁, Р₂, …, Р_к-1 смежные, то цепочка называется…

1. ассоциативной

2. эквивалентной

3. индуктивной

4. дедуктивной

В алгоритме Маркова дана цепочка Р Р₁, Р₂ ... Р_к. Если слова Р₁, Р₂, ..., Р_к-1 смежные и цепочка существует и в обратную сторону, то слова Р₁ и Р_к называют…

1. ассоциативными

2. эквивалентными

3. индуктивными

4. дедуктивными

В алгоритмах Маркова дана система подстановок в алфавите Л = {а, b, с}: abc — с ba — cb ca — ab Преобразуйте с помощью этой системы слово bacaabc.

1. cbc

2. ccbcbbc

3. cbacba

4. cbabc

В алгоритмах Маркова дана система подстановок в алфавите А = {а, b, с}: cb — abc Ьас — ас cab — b. Преобразуйте с помощью этой системы слово bcabacab.

1. ccb

2. cab

3. cbc

4. bcaab