Тест "Машина Тьюринга"
тест по теме

Тест «Машина Тьюринга»

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

1. Переместить ленту вправо
2. Переместить ленту влево
3. Остановить машину
4. Занести в ячейку символ

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

1. Переместить ленту вправо
2. Переместить ленту влево
3. Остановить машину
4. Занести в ячейку символ

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

1. Переместить ленту вправо
2. Переместить ленту влево
3. Остановить машину
4. Занести в ячейку символ

4. В машине Тьюринга рабочий алфавит:

1. А = {a40 0, b40 1, c40 2, … , w40 t};              
2. А = {a40 0, a40 1, a40 2, … , a40 t};
3. А = {a40 0, a41 0, a42 0, … , a4t 0};  
4. А = {a10 0, a20 0, a30 0, … , a90 0}

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

1. {a40 0, a40 1,a402, …,a40 t};                
2. {q41, q42, q43, …, q4s};
3. {q41, q42, q43, …, q4s, a40 0, a40 1, a40 2,…,a40 t};    
4. {q40, q41, q42, …, q4s}.

6. Результат применения команды машины Тьюринга  к машинному слову

7. Результат применения команды машины Тьюринга  к машинному слову

8. Результат применения команды машины Тьюринга  к машинному слову

                 2)

9. Конфигурация машины Тьюринга, соответствующая начальному стандартному положению

10. Конфигурация машины Тьюринга, соответствующая заключительному стандартному положению

11. Машина Тьюринга задана функциональной схемой

В какое слово переработает машина слово , исходя из стандартного начального положения

1. 0110                 2)011110
2. 01111                 4)011100

12. Установите соответствие

13. Конфигурация (машинное слово), соответствующая изображению

14. Если значение вычислимой по Тьюрингу функции f(x1, …, xn) не определено, то …

1. Машина останавливается через конечное число шагов, на ленте записано пустое слово
2. Машина останавливается через конечное число шагов, на ленте записано исходное слово
3. Машина останавливается через конечное число шагов, на ленте записано слово «error»
4. Машина работает бесконечно

15. Функция f(x1, x2) является вычислимой по Тьюрингу. Для вычисления значения f(1,3) начальная конфигурация имеет вид

1. 0101110
2. 010111q10
3. 1*111
4. 1*11q11

16. Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой

Формульное выражение функции f(x) имеет вид

17. Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой

Значение функции f(2) равно …

18. Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой

Значение функции f(2) равно …

19. Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой

Значение функции f(0) равно …

20. Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой