Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 187240
31.03.2013, 14:35
112.61 руб.
0 10 1
Компьютеры Программирование
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Построить машину Тьюринга для перевода из одной конфигурации в другую. На ленте всех машин Тьюринга записаны лишь нули и единицы, при этом пустые ячейки содержат нули. ( x , y ,z[$8805$]1) Проверить работу машины Тьюринга для конкретных значений x , y , z .

Обсуждение

давно
Лысков Игорь Витальевич
Посетитель
7438
7205
31.03.2013, 21:54
общий
Здравствуйте.

Условие неоднозначное: что делать, когда x > 2 и z [$8805$] 3
и, соответственно, x [$8804$] 2 и z < 3 ?
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Неизвестный
01.04.2013, 08:39
общий
Адресаты:
здравствуйте, у меня дано только такое условие,больше в задании ничего не указано.
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
01.04.2013, 10:56
общий
Спросить у преподавателя не пробовали?
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Неизвестный
01.04.2013, 11:02
общий
Адресаты:
попробую спросить,просто я на дистанционном,и преподаватель ответит не сразу,а как быть со сроком до закрытия консультации?
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
01.04.2013, 11:13
общий
Постарайтесь побыстрее. Срок действия консультации я продлил на 5 суток...
Пока буду обдумывать, как сделать...
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Неизвестный
01.04.2013, 11:15
общий
Адресаты:
хорошо, спасибо, я отправил преподавателю вопрос,буду ждать ответа,
Неизвестный
02.04.2013, 07:29
общий
Адресаты:
вот что ответил преподаватель - В задании необходимо построить машину Тьюринга, в вашем задании в начальный момент на ленте записаны три группы единиц в количестве х,у,z соответственно (х,у,z>0). По окончании работы машины на ленте должна быть одна
группа единиц в количестве x+z, если х>2 и z<3 в противном случае на ленте не должно быть единиц
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
02.04.2013, 10:44
общий
Хорошо. Теперь другое дело ...
Ок, постараюсь сделать...
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Неизвестный
02.04.2013, 11:04
общий
Адресаты:
постарайтесь,спасибо
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
06.04.2013, 04:11
общий
это ответ
Здравствуйте, Посетитель - 395932!
По условию, все x, y, z - ненулевые
Программа для машині Тьюринга приведена в таблице с подробными комментариями.
[table]
[row][col]№[/col][col]
0
[/col][col]
1
[/col][col]Комментарий[/col][/row]
[row][col]1[/col][col] [/col][col]1 П 2 [/col][col]0 невозможен, после первой 1x считаем x [/col][/row]
[row][col]2[/col][col]0 Л 18[/col][col]1 П 3[/col][col]если 0, то x=1 <= 2 и идем на обнуление, 1- считаем дальше[/col][/row]
[row][col]3[/col][col]0 Л 18[/col][col]1 П 4[/col][col]если 0, то x=2 <= 2 и идем на обнуление, 1- считаем дальше[/col][/row]
[row][col]4[/col][col]0 П 5[/col][col]1 П 4[/col][col]нашли 0 - идем на обнуление 1y, 1 - ищем 0[/col][/row]
[row][col]5[/col][col]0 П 6[/col][col]0 П 5[/col][col]0 - нашли второй 0, считаем 1z, 1 - обнуляем и ищем конец [/col][/row]
[row][col]6[/col][col] [/col][col]1 П 7[/col][col]0 невозможен, нашли первую 1 из 1z[/col][/row]
[row][col]7[/col][col]0 Л 9[/col][col]1 П 8[/col][col]0 - z=1, условие выполнено, складываем x+z, 1 - считаем дальше[/col][/row]
[row][col]8[/col][col]0 Л 9[/col][col]1 П 22[/col][col]0 - z=2, условие выполнено, складываем x+z, 1 - z>=3 и идем на обнуление[/col][/row]
[row][col]9[/col][col] [/col][col]0 Л 10[/col][col]начало цикла складывния x+z: обнуляем последнюю 1 и идем влево [/col][/row]
[row][col]10[/col][col]0 Л 16[/col][col]1 Л 11[/col][col]0 - была последняя 1, идем на ее добавление, 1 - добавляем непоследнюю 1 (еще вернемся) [/col][/row]
[row][col]11[/col][col]0 Л 12[/col][col]1 Л 11[/col][col]0 - нашли начало 1z, 1 - продолжаем искать начало [/col][/row]
[row][col]12[/col][col]0 Л 12[/col][col]1 П 13[/col][col]0 - ищем конец 1x, 1 - нашли, встанем на 0 за ними [/col][/row]
[row][col]13[/col][col]1 П 14[/col][col] [/col][col]добавим 1 в конце 1x [/col][/row]
[row][col]14[/col][col]0 П 14[/col][col]1 П 15[/col][col]0 - ищем 1 из 1z, 1 - нашли[/col][/row]
[row][col]15[/col][col]0 Л 9[/col][col]1 П 15[/col][col]0 - нашли конец 1z и на цикл переноса 1 до 1x, 1 - ищем 0 за 1z [/col][/row]
[row][col]16[/col][col]0 Л 16[/col][col]1 П 17[/col][col]последняя единица из1z!, 0 - ищем 1x, 1 - нашли[/col][/row]
[row][col]17[/col][col]1 Н 0[/col][col] [/col][col]найдена сумма x+z, останов [/col][/row]
[row][col]18[/col][col]0 П 19[/col][col]1 Л 18[/col][col]обнуление всех единиц для случая x<=2, ищем начало 1x[/col][/row]
[row][col]19[/col][col]0 П 20[/col][col]0 П 19[/col][col]0 - переход на обнуление 1y, 1 - обнуляем 1 из 1x[/col][/row]
[row][col]20[/col][col]0 П 21[/col][col]0 П 20[/col][col]0 - переход на обнуление 1z, 1 - обнуляем 1 из 1y[/col][/row]
[row][col]21[/col][col]0 Н 0[/col][col]0 П 21[/col][col]0 - все обнулено, останов, 1 - обнуляем [/col][/row]
[row][col]22[/col][col]0 Л 23[/col][col]1 П 22[/col][col]обнуление всех единиц для случая z>=3, ищем конец 1z[/col][/row]
[row][col]23[/col][col]0 Л 24[/col][col]0 Л 23[/col][col]0 - на поиск конца 1x, 1 - обнуляем[/col][/row]
[row][col]24[/col][col]0 Л 24[/col][col]0 Л 25 [/col][col]0 - ищем конец 1x, 1 - обнуляем и на обнуление всех остальных [/col][/row]
[row][col]25[/col][col]0 Н 0[/col][col]0 Л 25[/col][col]0 - все обнулено, останов, 1 - обнуляем[/col][/row]
[/table]
На ленте можно задать такие данные:
11101101 - получим 1111
1101101 - получим 0
111010111 - также получим 0
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Форма ответа