2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Машина Тьюринга, Нахождение модуля разности чисел
Сообщение11.05.2008, 22:54 


11/05/08
1
Задача такая:
Построить МТ, которая вычисляет модуль разности двух любых натуральных чисел. Указание: используйте сочетания МТ.

Проблема - плохо представляю себе как реализовать вычитание чисел, и совсем не представляю что такое "сочетания МТ". Ну теоретически то понятно, но как это реализоввывать не знаю. Теорию по МТ прочитала всю что смогла найти, все примеры пересмотрела, но они, к сожалению, все на каком то примитивном уровне типа "Определить четное число или нечетное".

ПОмогите пожалуйста, если не сложно, хотя бы идею для алгоритма подкиньте - реализовать то смогу...

Заранее спасибо.

 Профиль  
                  
 
 
Сообщение12.05.2008, 05:11 
Заслуженный участник
Аватара пользователя


21/12/05
5904
Новосибирск
BpeDuHa писал(а):
все на каком то примитивном уровне

А эта сложнее что ли?
Петя и Вася заспорили - у кого конфет больше и насколько? Считать они ещё не умеют. Как им материально эту разность представить?

 Профиль  
                  
 
 
Сообщение12.05.2008, 09:28 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
bot писал(а):
А эта сложнее что ли?
Петя и Вася заспорили - у кого конфет больше и насколько? Считать они ещё не умеют. Как им материально эту разность представить?

А эта?
Паниковский, Балаганов, Козлевич и Бендер делят кучу яблок.
Считать они ещё не умеют. Как им материально поделить?

 Профиль  
                  
 
 Re: Машина Тьюринга, Нахождение модуля разности чисел
Сообщение12.05.2008, 10:53 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
BpeDuHa писал(а):
...совсем не представляю что такое "сочетания МТ".


Я тоже. Несмотря на то, что каждый год читаю на мехмате лекции про эти самые машины Тьюринга :?

С машинами Тьюринга ведь в чём сложность?.. Они существуют в куче различных модификаций. В разных университетах на разных курсах разные лекторы определяют их чуть-чуть по разному, и часто каждый привносит что-то своё. Универсального для всех стандарта не существует. Студенты, слушающие какой-то один курс в каком-нибудь одном ВУЗе свято уверены, что понятия, которые им дают на лекциях, универсальны, но... зачастую это не так. Весь мир примерно знает о том, что такое машины Тьюринга, однако когда начинают уточнять определения. то детали у всех вылазят свои.

Машины Тьюринга бывают с одной лентой, с несколькими лентами, с бесконечным числом лент, с прямым и последовательным доступом к ячейкам... Ленты бывают как бесконечными с обоих концов, так и с одного конца, причём для лент, бесконечных с одного конца, граничную ячейку ленты иногда выделяют, а иногда нет. Даже на наиболее распространённой машине с одной лентой и последовательным доступом к ячейкам команды бывают как "пятисимвольные" (допускается одновременный сдвиг и запись в ячейку), так и "четырёхсимвольные" (подобное не допускается)... Числовые данные иногда записывают в двоичном коде, а иногда просто количество единиц обозначает число. Иногда допускается расширение внешнего алфавита, а иногда не допускается. И т. д., и т. п.

Темы "помогите написать программу для машины Тьюринга" время от времени возникают на этом форуме. И рады бы помочь, но... мы ведь тут не телепаты. И не можем угадать, какая именно модификация машины с какой именно системой команд принята в том конкретном ВУЗе и на том конкретном курсе/потоке, где учится спрашивающий. А без этой конкретики никто ведь программу не напишет! В лучшем случае можно будет дать общие указания к алгоритму.

Так что, уважаемый аскер... если хотите конкретной помощи, то давайте нам погружение в свой курс: с формулировками определений, примерами программ и т. д. Что касается каких-то общих указаний по алгоритму, то они уже были высказаны выше: головка машины бегает от одного аргумента к другому, отнимая от каждого по единице до тех пор, пока один из аргументов не обнулится; после обнуления одного из аргументов второй будет равен результату вычислений.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group