Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Машины Тьюринга. Тезис Черча-Тьюринга.




Заказать ✍️ написание работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

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. Начальная конфигурация машины Тьюринга имеет вид: 110Q11.
После выполнения программы

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

Какой алгоритм реализует данная машина Тьюринга?

+ сложения двух унарных чисел

– вычитания двух унарных чисел

– сложения двух унарных чисел и вычитания из результата тройки

– вычитания тройки из первого числа


Воспользуйтесь поиском по сайту:



©2015- 2022 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7