Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 9

Основы теории вычислимых функций - тест 9

Упражнение 1:

Номер 1

Машина Тьюринга включает объект:

Ответ:

(1) алфавит

(2) пустой символ

(3) множество выполняемых условных команд перехода

Номер 2

Машина Тьюринга включает объект:

Ответ:

(1) множество состояний

(2) команду присваивания

(3) команду цикла

Номер 3

Машина Тьюринга включает объект:

Ответ:

(1) таблицу выходных сигналов

(2) таблицу переходов

(3) заключительное состояние

Упражнение 2:

Номер 1

 Таблица переходов машины Тьюринга - функция:

Ответ:

(1) одного числа

(2) пар чисел

(3) троек чисел

Номер 2

 Таблица переходов машины Тьюринга - функция:

Ответ:

(1)

(2)

(3)

Номер 3

Конфигурация машины Тьюринга в каждый момент времени складывается из:

Ответ:

(1) содержимого ленты

(2) текущей позиции головки

(3) текущего состояния машины

Упражнение 3:

Номер 1

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

Ответ:

(1) 1 позицию влево

(2) 1 позицию вправо

(3) n>0 позиций влево

Номер 2

Если входной алфавит машины Тьюринга состоит 0, 1 и пробела, то входным будет:

Ответ:

(1) 01110 11

(2) 110101

(3) 111111

Номер 3

Тезис Тьюринга:

Ответ:

(1) всякая функция вычислима на машине Тьюринга

(2) всякая вычислимая функция вычислима на машине Тьюринга

(3) всякая вычислимая функция моделирует машину Тьюринга

Упражнение 4:

Номер 1

Ассоциативное исчисление - это:

Ответ:

(1) конечный набор любых правил

(2) конечный набор правил-продукций

(3) любой набор слов и словарного запаса языка

Номер 2

В алфавите X слово P выводимо из слова Q, если:

Ответ:

(1)

(2)

(3)

Номер 3

Если , то это множество:

Ответ:

(1) перечислимо

(2) не перечислимо

(3) универсально

Упражнение 5:

Номер 1

Если , то:

Ответ:

(1) Т - разрешимо для любого исчисления

(2) есть исчисление, для которого Т не разрешимо

(3) Т - всегда конечно

Номер 2

Инструкции "находясь в состоянии  и читая символ  перейти в состояние для всех , напечатать символ  и сдвинуться влево" соответствует:

Ответ:

(1)

(2)

(3)

Номер 3

Инструкция "находясь в состоянии s и читая символ x, перейти в состояние p, напечатать символ y и сдвинуться вправо" порождает правило:

Ответ:

(1)

(2)

(3)

Упражнение 6:

Номер 1

Ассоциативное исчисление - двустороннее, если оно содержит правила:

Ответ:

(1)

(2)

(3)

Номер 2

Двухстороннее исчисление, для правил которого нет алгоритма, выясняющегося, можно ли получить одно слово из другого:

Ответ:

(1) не существует

(2) существует

(3) неопределенно

Номер 3

Непустое множество с ассоциативной операцией типа умножения и единичным элементом называется:

Ответ:

(1) группой

(2) полугруппой

(3) полем

Упражнение 7:

Номер 1

Конкатенация - это операция:

Ответ:

(1) приписывания слова к слову слева

(2) приписывания слова к слову справа

(3) вставки слова в слово

Номер 2

Свободная полугруппа - это полугруппа:

Ответ:

(1) слов с операцией конкатенации

(2) слов с операцией вставки

(3) в которой еще не определена операция

Номер 3

Гомоморфизм полугрупп - это отображение:

Ответ:

(1) мультипликативное, с неподвижной точкой x=1

(2) ассоциативное, с неподвижной точкой x=1

(3) обратимое

Упражнение 8:

Номер 1

Совокупность элементов X и определённых над ними операции F, удовлетворяющих аксиомам, называется:

Ответ:

(1) арифметикой

(2) алгеброй

(3) множеством

Номер 2

Совокупность операций алгебры A называется:

Ответ:

(1) кортежем

(2) носителем

(3) сигнатурой

Номер 3

Совокупность операндов алгебры A называется:

Ответ:

(1) кортежем

(2) носителем

(3) множеством

Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 9