Машина_Тьюринг. Задание 34 а сложение
 Скачать 0.9 Mb.
|
|
Задание 1.34 А) сложение
Мы должны ввести нашу таблицу выше, в таблицу программы, предварительно задав алфавит А на линии ввести наш пример Вот как должно получиться  Делаем шаг  Следующий  Удалили одну единицу, следующий шаг  Далее  Мы заменили «+» на единицу. Наша программа на этом закончилась Проверим 11(2)+1(1)=111(3) Как мы видим наши единицы, сложил он верно  Б) вычитание
Такая таблица у меня получилась Как и в примере (а) ее нужно ввести в таблицу программы, поменять алфавит и выставить на ленте наш произвольный пример  Делаем шаг  Делаем следующий  Удалилась одна единица  Следующий  Следующий  Далее  Далее  Удалилась еще одна единица, другими словами, мы ее вычли.  Далее  Далее  Далее  Удалилась еще одна единица, но удалилась она для переноса вместо минуса. Перенос будет на следующих шагах    Вот и сам перенос Проверим 11(2)–1(1) =1(1) – верно В) умножение Таблица получилась следующая, здесь введены специальный обозначения, они являются метками, что упрощает написание.  Делаем шаг  Далее  Далее  Далее  Далее  Далее   Здесь мы поставили нашу метку, которая говорит нам о том, что нам нужно быть повторить первое число один раз после равно, что будет на последующих шагах     Мы поставили снова метку, которая говорит нам о том, что одну единицу мы уже переносим. Далее шаги будут идти вправо до икса, который мы заменим на единицу, икс является также меткой.       Мы поставили снова метку, чтоб нам ее снова заменить на единицу, далее мы пойдем до следующей единицы, заменим ее на метку «а» и будем переносить единицу на место икса.        Забрали единицу, идем к иксу.         Поставили единицу вместо икса, и поставили икс снова. Далее шаги будут такие же как выше, поэтому покажу результат этого действия  Вот как мы видим тот же самый алгоритм, единицу забрали поставили метку «а», перенесли на место икса, поставили икс рядом Выполняем далее            Мы пошли в обратную сторону, так как у нас больше нет единиц, которые нужно переносить. Делаем дальше шаги.  Раз у нас все единицы закончились, то нужно наши метки поменять обратно на единицы.     Смотрим на этом этапе, мы видим, что нам нужно еще раз перенести все единицы, снова поставим метку и будем переносить       Как мы видим все шаги повторяются с предыдущими, так будет до тех пор, пока у нас не кончаться единицы, поэтому покажу сразу результат этих действий.  Вот наша каретка перенесла все единицы.  Далее мы просто будем двигаться по единицам, поэтому покажу шаги после равно.   Здесь мы будем так же двигаться без изменений выражений до икса. Поэтому покажу сразу после него.     Мы снова заменяем метки на единицы.       Так как у нас не оказалось больше единиц во втором числе, значит мы уже умножили на нужное количество раз, поэтому мы просто заменим эти метки так же на единицы.   Наша программа окончена  Мы вернули наш пример в исходный вид, но при этом посчитали чему он равен. Проверим 111(3)*11(2)=111111(6) – наш программа работает корректно |
Q2
1
Q1