Задачи:
1. Описать первые 5 шагов работы машины Тьюринга из примера 2а при начальном состоянии, когда во всех ячейках записаны пустые символы λ. Указание: в этой и в других задачах под «описанием работы по шагам» имеется в виду просто вид ленты (что записано или «напечатано» в её ячейках на данном шаге, где находится головка машины и в каком она состоянии).
2. Описать работу машины Тьюринга из примера 4а для сложения чисел 2 и 3.
4. Описать работу машины Тьюринга из примера 5 для x, равного 2.
6. Описать работу машины Тьюринга из примера 8 при умножении 2 на 3.
7. Какую функцию f(x) вычисляет машина Тьюринга со следующей системой команд:
q10→ q20R, q11→ q01, q20→ q01, q21→ q21R ?
8. Построить машину Тьюринга, вычисляющую f(x) = x + 1 (построить машину – значит задать множество состояний, алфавит ленты и систему команд, а также описать её работу на простом примере.
9. Построить машину Тьюринга, выполняющую операцию дизъюнкции.
Прикрепленные файлы: |
|
|---|---|
|
Администрация сайта не рекомендует использовать бесплатные работы для сдачи преподавателю. Эти работы могут не пройти проверку на уникальность. Узнайте стоимость уникальной работы, заполните форму ниже: Узнать стоимость |
|
Скачать файлы:
|
Скриншоты работы: |
|
|---|---|
|
|