2015-01-30
304
1. Команда (
, 
) 
(
, Л, 
) определяет переход Машины Тьюринга из состояния … в состояние …
2. Команда (, ) (, Л, ) определяет следующую замену символов на ленте Машины Тьюринга…
3. Система команд: 
определяет следующую программу машины Тьюринга…
4. Машина Тьюринга задана системой команд: .
После двух тактов ее работы слово 
переработается в слово 
:
A) = 00 ; B) = ; C) = ;
D) = ; E) =0 .
5. Машина Тьюринга задана своей программой:
|
| |||
| 
| 
| 
|
| 
| 
| 
|
После двух тактов ее работы слово 
переработается в слово 
6. Машина Тьюринга задана своей программой:
|
| |||
|
| 
|
| 
|
После трех тактов ее работы слово переработается в слово
7. Нуль-функция (в двоичной системе счисления) реализуется с помощью Машины Тьюринга, заданной следующей программой:
| A) |
| |||
|
|
| 
|
|
| B) |
| |||
|
| 
|
|
|
| C) |
| |||
|
|
|
|
|
| D) |
| |||
|
|
|
|
|
| E) |
| |||
|
| 
| 
|
|
8. Функция 
(в двоичной системе счисления) реализуется с помощью машины Тьюринга, заданной следующей программой…
9. Функция следования 
(в двоичной системе счисления) реализуется с помощью машины Тьюринга, заданной программой…
10. Простейшей является следующая функция:
A) 
; B) 
; C) 
;
D) 
; E) 
.
11. Простейшей является следующая функция:
A) ; B) 
; C) 
;
D) 
; E) .
12. Значение функции проектора 
равно…
13. Значение функции 
при 
равно…
14. Суперпозицией функций 
и 
, 
, 
является k-местная функция при 
равном…
15. Суперпозицией функций 
, 
и 
является следующая функция:
A) 
; B) 
;
C) 
; D) 
; E) 
.
16. Суперпозицией функций 
и 
, 
является следующая функция…
17. Суперпозицией функций 
и 
является функция…
18. В результате работы оператора минимизации из k-местной функции получается m-местная функция для:
A) 
; B) 
; C) 
;
D) 
; E) 
.
19. В результате работы оператора примитивной рекурсии из k и m местных функций получается l-местная функция для:
A) 
; B) 
;
C) 
; D) 
;
E) 
.
20. Если заданы функции 
и 
, и 
получена из данных с помощью оператора примитивной рекурсии, то 
равно…
21. Если заданы функции и , и получена из данных с помощью оператора примитивной рекурсии, то 
22. Если заданы функции 
и S(x), и 
получена из данных с помощью оператора примитивной рекурсии, то 
равно:
A) 
; B) 
; C) 
; D) 
;
E) 
.
23. Если задана 3-местная функция и 
- 2-местная функция полученная из с помощью оператора минимизации, то 
тогда и только тогда, когда:
A) 
; B) 
;
C) 
; D) 
;
E) , где 
.
24. Если 
и 
получена из с помощью оператора минимизации, то 
равно…
25. Если = и получена из с помощью оператора минимизации, то равно…
26. Алгоритмически разрешимой является следующая проблема:
A) непротиворечивости формул алгебры высказываний;
B) непротиворечивости формул алгебры предикатов;
C) 10-ая проблема Гильберта;
D) остановки машины Тьюринга;
E) распознавания «тождества» слов в группе.
27. Алгоритмически неразрешимой является следующая проблема:
A) непротиворечивости исчисления высказываний;
B) непротиворечивости исчисления предикатов;
C) разрешимости квадратных уравнений в поле действительных чисел;
D) разрешимости линейных уравнений в поле действительных чисел;
E) разрешимости системы линейных уравнений в поле действительных чисел.
28. Функция называется примитивно-рекурсивной, если она может быть получена из…
29. Верно следующее утверждение:
A) примитивно-рекурсивная функция не является общерекурсивной;
B) примитивно-рекурсивная функция не является частично-рекурсивной;
C) общерекурсивная функция является примитивно-рекурсивной;
D) общерекурсивная функция является частично-рекурсивной;
E) частично-рекурсивная функция является общерекурсивной.
30. Функция является
A) частично-рекурсивной, но не примитивно-рекурсивной;
B) примитивно-рекурсивной;
C) примитивно-рекурсивной, но не общерекурсивной;
D) не общерекурсивной;
E) не частично-рекурсивной.
31. Всякая простейшая функция:
A) не является общерекурсивной;
B) не является частично-рекурсивной;
C) является общерекурсивной, но не частично-рекурсивной;
D) является примитивно-рекурсивной и частично-рекурсивной;
E) является общерекурсивной, но не примитивно-рекурсивной.
32. Из тезиса Чёрча-Тьюрнга следует, что класс функций, вычислимых на машине Тьюринга совпадает с классом функций:
A) примитивно-рекурсивных;
B) частично-рекурсивных;
C) общерекурсивных;
D) частично-рекурсивных, но не общерекурсивных;
E) общерекурсивных, но не примитивно-рекурсивных.
