Проверить работу машины Тьюринга над некоторыми словами. 

Заглавная страница
Избранные статьи
Случайная статья
Познавательные статьи
Новые добавления
Обратная связь
FAQ
Написать работу

КАТЕГОРИИ:

Археология
Биология
Генетика
География
Информатика
История
Логика
Маркетинг
Математика
Менеджмент
Механика
Педагогика
Религия
Социология
Технологии
Физика
Философия
Финансы
Химия
Экология

ТОП 10 на сайте

Приготовление дезинфицирующих растворов различной концентрации

Техника нижней прямой подачи мяча.

Франко-прусская война (причины и последствия)

Организация работы процедурного кабинета

Смысловое и механическое запоминание, их место и роль в усвоении знаний

Коммуникативные барьеры и пути их преодоления

Обработка изделий медицинского назначения многократного применения

Образцы текста публицистического стиля

Четыре типа изменения баланса

Задачи с ответами для Всероссийской олимпиады по праву


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Влияние общества на человека

Приготовление дезинфицирующих растворов различной концентрации

Практические работы по географии для 6 класса

Организация работы процедурного кабинета

Изменения в неживой природе осенью

Уборка процедурного кабинета

Сольфеджио. Все правила по сольфеджио

Балочные системы. Определение реакций опор и моментов защемления

Проверить работу машины Тьюринга над некоторыми словами.

 

№
1.
2. , если , если
3. , если в данном слове количество букв a нечетно, bb, если четно
4. , сели n нечетно, , если n – четно.
5.
6.
7. , если слово начинается на ba, в других случаях
8. , если , bb, если
9. ab, если n – четно, xn, если n - нечетно
10. an, если xn-1=a, x1x2…xn-2ab, если xn-1=b
11. x1x3x2x4x5…xn
12. ax1x2…xn-2b
13. a, если n<4, x1…xn, если n>3
14. a a, если в данном слове число букв нечетно, x1x2…xn-1, если четно
15. , если x2=a, x1…xn, если x2=b
16. bab, если слово начинается на ab, x1x2 в других случаях
17. x1x2...xnb, если n – четно, bx1x2…xn, если n – нечетно
18. a b, если x2=a, x1…xn-1, если x2=b
19. , если n – нечетно, x1x2…xn-1xnxn, если n - четно
20. an, если x1=a, x2, если x1=b
21. x1x2…xn-1
22.
23. x1xnx2x3…xn-1
24. bnx1…xn
25. (ab)n
26. x1x2…xn-2xn-1xn
27. x1, если n – нечетно, xn, если n - четно
28. xnxn-1…x1
29.
30. ab, если слово начинается на ba, x1…xn-1 в других случаях

 

Задание 2.

1. Построить машину Тьюринга, вычисляющую числовую функцию .

Проверить работу построенной машины над некоторыми наборами значений переменных.

 

№
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

Задание 3.

1. Написать формулу числовой функции , вычислимой машиной Тьюринга с множеством внутренних состояний , где 0 – заключительное, а 1 – начальное состояния, если машина задана своей программой.

Проверить работу машины Тьюринга с некоторым набором значений аргументов.

№ n            
    1П2 1П3 П4 Л5 Л5 Н0
  П1 1П2 1П3 П4 Л6 Л0
    --- 1П5 П4 Н0 --- Н0
  1П2 П3 П3 П4 1П6 П6
    П2 П3 Л4 1Н0 1Л6 1Л4
  П1 П2 1П3 П5 1П5 1Л6
    1П4 Л3 Н0 1Л5 1П6 1Н0
  1П2 1П1 Л3 1П4 1Л5 1П6
    --- 1П3 П4 Л5 Л5 1Н0
  П2 П2 1П3 1Л6 1Л6 1Л6
    П2 1П3 П4 Л5 Л5 ---
  П1 1П2 1П3 П4 Л6 Н0
    П4 1П3 1П1 Л5 Л5 Н0
  Л2 1Л2 1П3 П4 Л6 1Л6
    1П2 1П3 1П4 Л5 Л6 Л6
  1П1 П2 1П3 --- Л5 1Н0
    1П2 1П3 Л4 Л4 1Л6 1Л0
  П1 1П2 П3 Л5 1Л5 ---
    П2 П3 П4 Л5 Л5 1Н0
  П1 П2 1П3 П4 Л6 1Л6
    П2 1Н0 1П5 1Н0 1Л6 1Н0
  П1 1П3 1П4 1П4 1Л5 1Л6
    П2 1П3 1Л4 1П5 1Л6 1Н0
  П1 П2 1П3 1Л4 1П5 1Л6
    1П4 1П3 1П1 1П5 1П6 Н0
  Л2 1Л2 1П3 1П4 --- 1Н0
    Н0 П3 1П4 1П5 --- 1Л1
  Н2 П2 П3 1П4 1Л6 1Л6
    1П2 Л3 1П6 1Л5 1Л3 1Н0
  1П1 1П2 П4 1П4 1Л5 1П6
    1П2 П3 П4 Л5 Л5 1Н0
  1П1 П2 П3 П4 1Л6 1Л6
    П2 П3 П4 Л5 Л5 1Н0
  1П1 П2 П3 П4 1Н6 1Л6
    1П2 1П3 Л4 Н0 1Л6 1Л4
  1П1 1П2 1П3 П5 1П5 1Л6
    1П2 1П3 Л4 Л4 1П6 1Н0
  П1 1П2 П3 1Л5 1Л5 1П6
    1П1 1Н0 1П5 Н0 1П6 1Н0
  1П2 1П3 1П4 П4 1Л0 ---
    --- 1П3 П4 П5 Л6 Л6
  П2 1П2 1П3 П4 П5 Н0
    1П2 1П3 1Л4 1Л5 Л5 Н0
  1П1 П2 1П3 1Л4 1Н6 Л6
    1Н0 П5 1П4 1Н0 1П6 1П1
  П2 1П3 1П3 1П4 П5 1П6
    П2 1П3 1П4 1П5 Л6 Л6
  П1 П2 1П3 1П4 П5 Н0
    1П2 Н0 1П4 1П2 1П6 1Н0
  П1 Л3 1Л3 1П4 1Л6 1Н0
    1П2 П3 --- 1Л5 1Н0 1Н0
  1П1 1П2 1П4 1Л6 1Л5 1Л6
    1П2 --- 1Н0 1Л5 1П6 1П3
  1П1 1П3 1П4 1П4 1Л5 1П6
    1П2 1Л3 1П4 1Л5 1П6 Н0
  1Л1 1П2 1Л3 1П4 1Л5 1П6
    1П2 --- П4 Л5 Л5 1Н0
  П1 П3 1П3 П4 Л6 1Л6
    1П2 Л5 Л4 1Н0 1Л6 1П0
  1П1 1П3 1П2 Л4 1Л5 Л6

Задание 4.

1. По данному коду N(T) восстановить программу машины Тьюринга.

Выяснить, является ли машина Тьюринга самоприменимой или несамоприменимой.

При составлении N(T) использована следующая кодировка:

П – 1, Л – 12, Н – 13, - 14, 1 – 15, * - 16, s0 – 17, s1 – 18, s2 – 19.

№ N(T)
1. 18*14*1*19**18*15*1*18**18*16*14*12*18** 19* 14*14*13*19**19*15*15*1*19**19*16*14*1*18
2. 18*14*14*1*17**18*15*16*1*19**16*15*12*19** 19* 14*14*1*18**19*15*15*1*18**19*16*15*1*19
3. 18*14*14*1*18**18*15*16*12*17**18*16**15*13*17** 19* 14*14*13*17**19*15*16*1*19**19*16*16*1*18
4. 18*14*14*12*19**18*15*16*12*18**18*16*15*13*18** 19*14*14*1*19**19*15*16*12*18**19*16*14*1*18
5. 18*14*14*12*17**18*15*16*12*19**18*16*16*13*19** 19*14*14*12*18**19*15*15*12*17**19*16*15*1*19
6. 18*14*14*12*18**18*15*14*13*17**18*16*16*1*17** 19* 14*14*1*17**19*15*15*13*19**19*16*16*1*18
7. 18*14*14*13*19**18*15*14*13*18**18*16*16*1*18** 19* 14*14*12*19**19*15*16*12*18**19*16*14*1*18
8. 18*14*14*13*17**18*15*15*13*19**18*16*16*1*19** 19* 14*14*1*18**19*15*16*13*19**19*16*15*1*18
9. 18*14*14*13*18**18*15*14*1*17**18*16*16*12*17** 19* 14*14*1*17**19*15*14*1*18**19*16*16*1*19
10. 18*14*14*1*19**18*15*14*1*18**18*16*16*12*18** 19* 14*14*12*18**19*15*15*13*17**19*16*14*1*19
11. 18*14*15*1*17**18*15*14*1*19**18*16*16*12*19** 19*1 14*14*12*19**19*15*16*1*19**19*16*15*12*17
12. 18*14*15*1*18**18*15*14*13*17**18*16*16*13*17** 19* 14*16*12*17**19*15*14*1*19**19*16*16*12*18
13. 18*14*15*12*19**18*15*14*12*18**18*16*16*13*18** 19*14*16*13*18**19*15*15*12*18**19*16*14*12*18
14. 18*14*15*12*17**18*15*14*12*19**18*16*14*13*19** 1 19*14*13*19**19*15*16*12*18**19*16*15*12*18
15. 18*14*15*12*18**18*15*14*12*17**18*16*14*1*17** 19*14*16*13*17**19*15*14*13*17**19*16*16*12*18
16. 18*14*15*13*19**18*15*14*12*18**18*16*14*1*18** 19*14*16*1*19**19*15*14*12*19**19*16*14*12*19
17. 18*14*15*13*17**18*15*14*13*19**18*16*14*1*19** 19*14*16*1*18**19*15*15*13*19**19*16*15*12*19
18. 18*14*15*13*18**18*15*15*13*17**18*16*14*12*17** 19*14*16*1*17**19*15*16*13*18**19*16*16*12*17
19. 18*14*15*1*19**18*15*15*13*18**18*16*14*12*18** 19*14*16*12*19**19*15*14*11*18**19*16*14*12*19
20. 18*14*16*1*17**18*15*15*13*19**18*16*14*12*19** 19*14*16*12*18**19*15*14*12*17**19*16*15*1*19
21. 18*14*16*1*18**18*15*15*1*17**18*16*14*13*17** 19*14*15*12*17**19*15*15*12*19**19*16*16*1*18
22. 18*14*16*12*19**18*15*14*1*18**18*16*14*13*18** 19*14*15*13*19**19*15*16*1*18**19*16*14*1*19
23. 18*14*16*12*17**18*15*15*1*19**18*16*15*13*19** 19*14*15*13*18**19*15*16*12*19**19*16*15*1*17
24. 18*14*16*12*18**18*15*15*12*17**18*16*15*1*17** 19*14*15*13*17**19*15*15*12*19**19*16*16*1*19
25. 18*14*16*12*19**18*15*15*12*18**18*16*15*1*18** 19*14*15*1*19**19*15*16*13*18**19*16*14*12*19
26. 18*14*16*13*17**18*15*15*12*19**18*16*15*1*19** 19*14*15*1*18**19*15*14*13*18**19*16*15*13*18
27. 18*14*16*13*18**18*15*16*13*17**18*16*15*12*17** 19*14*15*1*17**19*15*15*1*18**19*16*16*13*17
28. 18*14*16*1*19**18*15*16*13*18**18*16*15*13*18** 19*14*15*12*19**19*15*16*13*17**19*16*14*13*18
29. 18*14*15*1*17**18*15*16*13*19**18*16*15*12*19** 19*14*15*13*18**19*15*15*1*19**19*16*15*1*18
30. 18*14*14*1*18**18*15*16*1*17**18*16*15*13*17** 19*14*14*12*17**19*15*14*1*18**19*16*16*12*17

 

ОБРАЗЕЦ ОФОРМЛЕНИЯ И ВЫПОЛНЕНИЯ ПРАКТИЧЕСКОЙ РАБОТЫ № 2.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

ПРИДНЕПРОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ СТРОИТЕЛЬСТВА И АРХИТЕКТУРЫ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

ПРАКТИЧЕСКАЯ РАБОТА № 2.

Тема: «МАШИНЫ ТЬЮРИНГА»

Выполнил студент группы _____

_____________________________

(Фамилия, имя, отчество)

Дата выполнения _____________

Дата защиты работы __________

Кол-во баллов: ______________

Подпись преподавателя:

Г. Днепропетровск - 2012

Задание 1.

3. Построить машину Тьюринга, применимую ко всем словам в алфавите и переводящую их в слово .

Проверить работу машины Тьюринга над некоторыми словами.

Решение:

1. Опишем работу алгоритма, решающего эту задачу.

Будем обозначать состояния машины Тьюринга числами 0, 1, 2, 3, …, причем 1 – начальное, а 0 – заключительное состояния.

Вначале с помощью команд проходим до конца слова, не изменяя его символов.

Признаком окончания слова будет считывание в первом состоянии.

С помощью команд движемся влево, не изменяя последнего символа.

Если в состоянии 3 считываем a, значит, , нужно стирать все символы слова , кроме последнего. Это можно сделать с помощью команд . Если в состоянии 4 считывается , значит, вся работа проделана, и пора останавливаться с помощью команды .

Если в состоянии 3 считываем символ b, значит, , нужно все символы, кроме xn, заменять буквами b. Это делаем с помощью команд . Если в состоянии 5 считывается , значит, все символы исходного слова пройдены, можно переходить в состояние 0 с помощью команды .

Запишем программу найденной машины Тьюринга в виде таблицы:

 

         
Л2 - - Н0 Н0
a a П1 a Л3 Л4 Л4 b Л5
b b П1 b Л3 b Л5 Л4 b Л5

 

2. Проверим работу построенной машины Тьюринга над словами abba:

Итак, в слове abba предпоследний символ – b, и все буквы исходного слова, кроме последней, заменены буквой b.

Проверим работу построенной машины Тьюринга над словом bbaaa:

В слове bbaaa предпоследний символ – a, и все буквы исходного слова, кроме последней, заменены пустыми символами .

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

 

 

Задание 2.

3. Построить машину Тьюринга, вычисляющую числовую функцию .



Поделиться:


Познавательные статьи:


Где возникла философия и почему?
Относительная высота сжатой зоны бетона
Сущность проекции Гаусса-Крюгера и использование ее в геодезии
Тарифы на перевозку пассажиров


Последнее изменение этой страницы: 2016-04-21; просмотров: 1324; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.216.156 (0.007 с.)