Консультация № 179831
01.09.2010, 11:05
35.82 руб.
01.09.2010, 11:48
0 6 1
Здравствуйте уважаемые эксперты профессионалы, пожалуйста решите две задачи:

1 Привести формулу к предваренной форме:


2 Построить машину Тьюринга для перевода из одной конфигурации в другую. На ленте всех машин Тьюринга записаны лишь нули и единицы, при этом пустые ячейки содержат нули. ( x , y ,z 1) Проверить работу машины Тьюринга для конкретных значений x , y , z .




За правильное решение двух задач обещаю поставить хорошо(40руб.)+хорошо(40руб.).

Обсуждение

Неизвестный
01.09.2010, 11:11
общий
Увеличенное изображение задачи 2:
давно
Профессор
230118
3054
01.09.2010, 17:42
общий
kapezc:
Разве решение 1 задачи неправильно?
давно
Посетитель
7438
7205
02.09.2010, 12:24
общий
это ответ
Здравствуйте, kapezc.

Предлагаю Вашему вниманию программу для машины Тьюринга (надеюсь, что с самой машиной Тьюринга Вы знакомы)
Алгоритм такой - отрабатываем два раза следующие шаги:
1) идем вправо и заменяем все 1 на #, в конце добавляем признак конца *
2) идем влево, пока не найдем 0 или 1, делаем шаг вправо
3) если *, то все прошли: ставим 0 и заканчиваем (либо на вторую половину, либо останов), если #, то восстанавливаем 1, делаем шаг вправо и на 4
4) ищем вправо признак конца *
5) идем вправо, пока не найдем 0 - меняем на 1, делаем шаг влево
6) ищем влево * и на шаг 2
[table]
[row][col][/col][col]
0
[/col][col]
1
[/col][col]
*
[/col][col]
#
[/col][col][/col][/row]
[row][col]
1
[/col][col]
* Л 2
[/col][col]
# П 1
[/col][col]
-
[/col][col]
-
[/col][col]Заменяем все 1 на #, в конце ставим *[/col][/row]
[row][col]
2
[/col][col]
0 П 3
[/col][col]
1 П 3
[/col][col]
-
[/col][col]
# Л 2
[/col][col]Ищем влево либо 0, либо 1[/col][/row]
[row][col]
3
[/col][col]
-
[/col][col]
-
[/col][col]0 П 7[/col][col]1 П 4[/col][col]Если *, то меняем на 0, и идем на повтор еще одной последовательности, если #, то меняем на 1 и идем на поиск конца, т.е. *[/col][/row]
[row][col]
4
[/col][col]
-
[/col][col]
-
[/col][col]* П 5[/col][col]# П 4[/col][col]Ищем *[/col][/row]
[row][col]
5
[/col][col]
1 Л 6
[/col][col]
1 П 5
[/col][col]
-
[/col][col]
-
[/col][col]Пропускаем 1, в конце добавляем еще одну 1[/col][/row]
[row][col]
6
[/col][col]
-
[/col][col]
1 Л 6
[/col][col]
* Л 2
[/col][col]
-
[/col][col]Ищем влево * и на поиск очередной #[/col][/row]
[row][col]
7
[/col][col]
* Л 8
[/col][col]
# П 7
[/col][col]
-
[/col][col]
-
[/col][col]7-12 строки полностью повторяют строки 1-6[/col][/row]
[row][col]
8
[/col][col]
0 П 9
[/col][col]
1 П 9
[/col][col]
-
[/col][col]
# Л 8
[/col][col][/col][/row]
[row][col]
9
[/col][col]
-
[/col][col]
-
[/col][col]0 Н 0[/col][col]1 П 10[/col][col]Единственное отличие - по звездочке будет останов[/col][/row]
[row][col]
10
[/col][col]
-
[/col][col]
-
[/col][col]* П 11[/col][col]# П 10[/col][col][/col][/row]
[row][col]
11
[/col][col]
1 Л 12
[/col][col]
1 П 11
[/col][col]
-
[/col][col]
-
[/col][col][/col][/row]
[row][col]
12
[/col][col]
-
[/col][col]
1 Л 12
[/col][col]
* Л 8
[/col][col]
-
[/col][col][/col][/row]
[/table]
В результате из последовательности, например, 1111 получим 11110111101111
5
Спасибо за решение.
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Неизвестный
02.09.2010, 15:28
общий
Цитата: Асмик Гаряка
kapezc:
Разве решение 1 задачи неправильно?


Как-то не заметил, сейчас оценю.

ЗАДАЧА 1 РЕШЕНА!!!!!
Неизвестный
02.09.2010, 15:38
общий
По второму вопросу(от Лыскова Игоря Витальевича ) оценю чуть по по же.
Неизвестный
03.09.2010, 11:26
общий
Цитата: 320784
По второму вопросу(от Лыскова Игоря Витальевича ) оценю чуть по по же.


Ставлю хорошо(40руб.)
Форма ответа