 |
Машины Тьюринга. Тезис Черча-Тьюринга.
|
|
|
|
1. За начальное состояние машины Тьюринга отвечает символ внутреннего алфавита …
– qn
– R
– q0
+ q1
2. За конечное состояние машины Тьюринга отвечает символ внутреннего алфавита …
– qn
– S
+ q0
– q1
3. Внешним алфавитом машины Тьюринга является …
+ A={ a0,a1,...,an}
– Q={q0,q1,...,qn}
– {R,L,S}
– {a, b, …}
4. Работа машины Тьюринга продолжается до тех пор, …
– пока команда сдвига не будет обозначать отсутствие сдвига – S
+ пока машина Тьюринга не придёт в состояние q0
– не будет получен результат вычисления
– не будут пройдены все непустые ячейки ленты
5. Лента машины Тьюринга …
– ограничена слева
– ограничена справа
– ограничена с обеих сторон
– не ограничена ни с одной стороны
6. Внутренним для машины Тьюринга является алфавит
– A={ a0,a1,...,an}
+ Q={q0,q1,...,qn}
– {R,L,S}
– {a, b, …}
7. Алфавитом сдвигов для машины Тьюринга является алфавит
– A={ a0,a1,...,an}
– Q={q0,q1,...,qn}
+ {R,L,S}
– {a, b, …}
8. Минимальным элементом памяти машины Тьюринга является (ячейка)
9. В ячейке ленты машины Тьюринга может храниться...
+ только одна буква внешнего алфавита
– только одна буква внутреннего алфавита
– произвольное количество букв внешнего алфавита
– произвольное количество букв внутреннего алфавита
10. Управляющая головка Машины тьюринга в каждый момент времени "умеет"...
+ обозревать, считывать и записывать символ в одной ячейке ленты
– обозревать, считывать и записывать символы в нескольких ячейках ленты, идущих подряд
– обозревать и записывать символ в одной ячейке ленты
– обозревать и считывать символ в одной ячейке ленты
11. Дана функциональная схема. На ленте машины Тьюринга изначально записано слово 10100. Головка машины находится в конфигурации стандартного начала (первый символ слова). Укажите, что будет записано на ленте после выполнения данной функциональной схемы.
|
|
|
– 10101
– 10110
+ 10011
– 11001
12. Дана функциональная схема. На ленте записано слово 1011. Головка машины Тьюринга находится в конфигурации стандартного начала (первый символ слова). Укажите первое действие, которое выполнит головка машины Тьюринга.
– сдвинется вправо на ноль в состоянии q1, заменив 1 на 0
– сдвинется влево, изменит состояние на q2 и заменит 1 на 0
+ сдвинется вправо на ноль в состоянии q1, ничего не меняя
– сдвинется влево, изменит состояние на q2 и сотрет 1
13. Дана функциональная схема машины Тьюринга. На ленте записано слово 13201. При выполнении функциональной схемы головка на ленте машины дошла до конца вправо и встала на пустой символ. Укажите следующее действие, которое выполнит головка.
– поставит вместо пустого символа единицу, сдвинется влево и перейдет в состояние q3
+ сдвинется влево не внося изменений в ячейку и встанет на последний символ слова (1), перейдя в состояние q2
– сдвинется вправо в состояние q0, стерев последний символ
– не произведя сдвига на ячейку поставит вместо пустого символа единицу и перейдет в состояние q0
14. Укажите, какую функцию вычисляет данная функциональная схема машины Тьюринга в четверичной системе счисления.
– x-4
– 3*x
– x+y
+ x+4
15. Укажите, какую функцию вычисляет данная функциональная схема машины Тьюринга
– 
+ 
– 
– 
16. Укажите, какую функцию вычисляет данная функциональная схема машины Тьюринга.
– f(x,y)=x+y
+ f(x)=1+x
– f(x)=x-1
– f(x,y)=x-y
17. Дана функциональная схема машины Тьюринга.Головка машины находится в конфигурации стандартного начала. На ленте записано слово 3210221. Введите слово, которое будет записано на ленте машины после выполнения работы (ответ вводится с клавиатуры без пробела).
(ответ: 1)
18. Дана функциональная схема машины Тьюринга. На ленте записано слово 30121. Головка машины Тьюринга находится на последнем символе слова (1). Введите, слово, которое будет записано на ленте машины после выполнения следующего шага работы (ответ вводится с клавиатуры без пробела).
|
|
|
(ответ: 30123)
19. Дана функциональная схема машины Тьюринга.Головка машины находится в конфигурации стандартного начала (первый символ слова). На ленте записано слово 1231. Введите, слово, которое будет записано на ленте машины после выполнения работы (ответ вводится с клавиатуры без пробела).
(ответ: 1301)
20. В модели машины Тьюринга внешняя память представлена в виде..., разделенной на секции одинакового размера – ячейки памяти.
– конечной ленты
– бесконечной вправо ленты
+ есконечной в обе стороны ленты
– конечной влево ленты
21. Конечное число символов, с помощью которых кодируется информация, подаваемая в машину, и информация, которая вырабатывается в процессе её работы, называется...
+ внешним алфавитом
– внутренним алфавитом
– совокупностью
– алфавитом
22. В модели машины Тьюринга нет элементарной команды …
+ B (Назад)
– R (Вправо)
– L (Влево)
– S (На месте)
23. Унарная запись натурального числа n - это набор, состоящий из...
– (n-1)-ого символа "|"
+ (n+1)-ого символа "|"
– n символов "|"
– (n+1)-ого символа "1"
24. Необходимо построить программу, реализующую алгоритм перевода слова из X палочек в слово из X+1 палочки. Каретка машины находится над крайней слева палочкой.
Какая из приведённых программ реализует этот алгоритм?
– Q0| --> |LQ1; Q1| --> |SQ1
– Q1| --> |RQ1; Q1| --> |SQ0
– Q1| --> |LQ1; Q1| --> |SQ1
+ Q1| --> |LQ1; Q1| --> |SQ0
25. Начальная конфигурация машины Тьюринга имеет вид: 110 Q1 1.
После выполнения программы
Q10 --> 1LQ2
Q11 --> 0LQ1
Q21 --> 0LQ3
Q20 --> 0RQ3
Q2^ --> 1SQ1
Q3^ --> ^RQ0
Q3 0--> 0LQ3
Q31 --> 1LQ3
будет получено слово...
– 1011
+ 1010
– 1111
– 1000
26. На ленте имеется два набора символов "|", разделённых двумя пустыми ячейками. Каретка машины находится под крайним справа символом "|" в первом наборе. Машина работает в соответствии с программой:
Q1| --> |LQ1
Q1^ --> |LQ2
Q2 ^ --> |LQ3
Q3| --> |LQ3
Q3 ^ --> ^RQ4
Q4| --> ^RQ5
Q5| --> ^RQ6
Q6| --> ^RQ0
Какой алгоритм реализует данная машина Тьюринга?
+ сложения двух унарных чисел
|
|
|
– вычитания двух унарных чисел
– сложения двух унарных чисел и вычитания из результата тройки
– вычитания тройки из первого числа
|
|
|
