Уменьшить на единицу число записанное в десятичной системе счисления машина тьюринга

Машина Тьюринга: уменьшить заданное число n на 1

Вложения

2.rar (255 байт, 85 просмотров)

Машина Тьюринга, умножающая число на 11
На ленте машины Тьюринга находится число, записанное в десятичной системе исчисления. Умножьте это.

Машина Тьюринга, умножающая число на 2
На ленте машины Тьюринга находится число, записанное в десятичной системе исчисления. Умножьте это.

Машина Тьюринга: поделить двоичное число с остатком
Дано трехразрядное двоичное число. Осуществить его деление на два с остатком. Число и остаток.

Машина Тьюринга: является ли унарное число степенью трёх
Построить машины Тьюринга для вычисления функций A=< | >. Считая слово P записью числа в.

Вложения

MT.rar (433 байт, 132 просмотров)

Для того, чтобы из 099 получить 99, необходимо добавить:

Оставить на ленте то число, которое больше (машина Тьюринга)
Дано два числа, записанных в унарной системе счисления, разделенных пустым символом. Оставить на.

Машина Тьюринга: умножить на 2 число в семеричной системе счисления.
Помогите пожалуйста На ленте машины Тьюринга находится целое положительное число, записанное в.

Машина Тьюринга: увеличить число в семеричной системе счисления на 2.
На ленте машины Тьюринга находится целое положительное число, записанное в семеричной системе.

Машина Тьюринга: оставить на ленте целое число от деления n на 3
Нужно построить функциональную схему Машины тьюринга которая оставляет на ленте целое число от.

Если заданное число больше 3, то увеличить число на 10, иначе уменьшить на 10
Помогите написать программу. Дано число. Если оно больше 3, то увеличить число на 10, иначе.

Уменьшить количество забитых шайб на заданное число, если это число больше 0
Привет. В ячейки K7 появляется общее количество забитых шайб. По нажатию на кнопку надо уменьшить.

Источник

Построить машину Тьюринга, которая записывала бы в десятичной системе счисления число этих единиц

Построить машину Тьюринга, которая увеличивает число, записанное в десятичной системе счисления, в 4 раза
Каким способом можно это записать? Помогите плес: Построить машину Тьюринга, которая.

Создать машину Тьюринга, которая прибавляет 1 к числу в восьмеричной системе счисления
Здравствуйте, помогите создать МТ которая прибавляет 1 к числу в восьмеричной сс. Например на.

Построить машину Тьюринга, которая умножает любое число машинного кода на 2
Помогите пожалуйста)Построить машину Тьюринга, которая умножает любое число машинного кода на 2.

Дано целое число X в десятичной системе счисления. Выведите запись числа X в восьмеричной системе счисления
Почему настоящие программисты путают католическое Рождестово и Halloween? Потому что 25 DEC = 31.

Можно показать реализацию 1 и 3 шага

q1 1 >q2 0 R
q2 1 > q2 1 R
q2 l > q3 * R
q3 > q4 1 L
q3 >.

Решение

Имелся ввиду шаг, на котором к десятичному числу прибавляется 1, при этом головка в начальном положении смотрит на старший разряд.

Добавлено через 29 минут

Далее надо написать программу прибавления единицы к десятичному числу, старший разряд Х которого встретился нам в состоянии q4. После этого прибавления головка должна в состоянии q3 смотреть на первый ноль слева от десятичного числа (такой 0 всегда будет).

Источник

Машина Тьюринга на формулах Excel

Что такое Машина Тьюринга

Простой пример: прибавление единицы к двоичному числу

Для такой машины потребуется алфавит из трех символов (0,1, х) – где 0 и 1 будут для числа, а х для пустой ячейки. То есть пустая лента вся заполнена символами «х».
У головки будет 4 состояния: q1,q2,q3 и q4 – остановка машины.
Правила для машины выпишем в виде матрицы:

Нетрудно проверить, что такая машина при помещении головки на старший разряд двоичного числа, при начальном состоянии q1, увеличит это число на 1.

Реализация на Excel

Создадим таблицу правил, как в примере выше. Выделим всю эту таблицу и назовем ее «rules». Жмем Enter.

Зададим начальное состояние ленты:

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

Формула для ячейки ленты:
=ЕСЛИ(K14<>0; ИНДЕКС(rules;K14+1;2+K13*3);K13)
Эта формула для значения ячейки ленты на следующем шаге (K17). Она означает, что если головка (K14) находится под ячейкой (то есть в клетке K14 не ноль), то следует записать в эту ячейку значение согласно правилам (из массива rules). Если же в клетке под ячейкой ленты ноль (что значит, под ней нет головки), то значение не меняется.

Формула для состояния головки (для удобства чтения сделаны переносы строки):
=ЕСЛИ(K14<>0; ЕСЛИ(ИНДЕКС(rules;K14+1;4+K13*3)=0; ИНДЕКС(rules;K14+1;3+K13*3);0);
ЕСЛИ(J14<>0; ЕСЛИ(ИНДЕКС(rules;J14+1;4+J13*3)=1; ИНДЕКС(rules;J14+1;3+J13*3);0);
ЕСЛИ(L14<>0; ЕСЛИ(ИНДЕКС(rules;L14+1;4+L13*3)=-1; ИНДЕКС(rules;L14+1;3+L13*3);0);0)))

Эта формула
1) сначала проверяет, находится ли головка в этой ячейке (K14) – тогда если правила говорят оставаться на месте, в эту клетку пишется состояние машины согласно правилам
2) Если головка находится на одну ячейку влево (J14) и правила говорят сдвинуться вправо – тогда в эту клетку пишется состояние машины согласно правилам
3) Если головка находится на одну ячейку справа (L14) и правила говорят сдвинуться влево – тогда в эту клетку пишется состояние машины согласно правилам
4) Во всех остальных случаях пишется ноль
Такая формула имитирует движение головки.
В формулах использована функция Индекс(массив, строка, столбец). Вычислим значение ИНДЕКС(rules;K14+1;4+K13*3) – кусочка формулы состояния головки.
Как видно из рисунка, K14=1, K13=1. Значит надо найти ИНДЕКС(rules;1+1;4+1*3) то есть ИНДЕКС(rules;2;7) – значение в массиве «rules» на пересечении 2й строки и 7го столбцы (нумеруются строки и столбцы начиная с 1, а не 0). В нашей табличке это значение «1».

Формулы относительные – то есть при копировании их на новые ячейки эксель берет данные из ячеек соответствующий предыдущему состоянию машины.
В итоге, выполнив все шаги, машина «останавливается» — достигнуто состояние «4», к числу прибавлена единица.

Вот ссылка на файл Excel

Заключение

Если бы Эксель поддерживал сколь угодно большое число строк и столбцов, то это автоматически означало бы, что используя формулы экселя можно реализовать любую вычислимую функцию, так как Excel был бы Тьюринг-полным

Источник

n1.doc

Машина Поста, Тьюринга и алгоритмы Маркова.

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»

Одним из центральных понятий информатики является понятие алгоритма. В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

Несмотря на “примитивность” машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый “тезис Поста”: “Всякий алгоритм представим в форме машины Поста”. Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.

Тезис Поста является гипотезой. Его невозможно строго доказать (так же, как и тезис Тьюринга), потому что в нем фигурируют, с одной стороны, интуитивное понятие “всякий алгоритм”, а с другой стороны — точное понятие “машина Поста”. Для того чтобы опровергнуть гипотезу Поста, необходимо придумать алгоритм, который невозможно записать в виде программы для машины Поста. На сегодняшний день такого алгоритма не существует.

Машина Поста — это абстрактная (т.е. не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию. Разработка программ для машин Поста — достаточно эффективный этап в обучении алгоритмизации, т.к. в процессе написания этих программ учащиеся учатся разбивать интуитивно понятные вычислительные процедуры на элементарные действия. Изучение машины Поста полезно как школьникам, интересующимся информатикой и математикой, так и студентам младших курсов, обучающимся по специальности “прикладная математика и информатика”. При этом теоретический материал доступен даже школьникам младших классов, но требует в этом случае некоторых методических поправок.

В статье предлагается материал для практикума по теме “Машина Поста” в рамках изучения основ алгоритмизации. Практикум включает в себя теоретическую часть и набор задач с решениями.

Источник

Глава 5. Элементы теории алгоритмов

Глава 5. Элементы теории алгоритмов

Практические работы

Практическая работа № 36.
Машина Тьюринга

1. Наберите программу из учебника (или из презентации), которая увеличивает двоичное число на 1 и проверьте её работу.

Будет ли правильно работать эта программа, если вначале каретка расположена справа от числа? Почему?

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

3. Опишите алгоритм работы программы для машины Тьюринга:

При каком начальном состоянии ленты и положении каретки эта программа зацикливается?

4. Составьте программу для машины Тьюринга, которая заменяет в двоичном числе все 0 на 1 и все 1 на 0 (из числа 10101100 получается 01010011). Каретка находится слева от числа.

5. Составьте программу для машины Тьюринга, которая умножает двоичное число на 2. Каретка находится над числом.

6. Составьте программу для машины Тьюринга, которая увеличивает троичное число на 1. Каретка находится справа от числа.

При каком начальном положении каретки эта программа зацикливается?

7. Составьте программу для машины Тьюринга, которая уменьшает двоичное число на 1. Каретка находится над числом.

При каком начальном положении каретки эта программа зацикливается?

8. Составьте программу для машины Тьюринга, которая умножает троичное число на 2. Каретка находится над числом.

9. Дана строка, состоящая только из символов «а» и «б». Составьте программу для машины Тьюринга, которая переставляет последний символ в начало строки. Каретка находится над первым символом строки.

10. *Дана строка, состоящая только из символов «а» и «б». Составьте программу для машины Тьюринга, которая сортирует символы, то есть переставляет все буквы «а» в начало строки. Каретка находится над первым символом строки. Используйте состояния, которые перечислены род таблицей.

q ₁ – каретка идёт вправо по цепочке букв «а»

q ₂ – каретка идёт вправо по цепочке букв «б»

q ₃ – каретка идёт влево и ищет конец цепочки букв «б»

11. *Составьте программу для машины Тьюринга, которая складывает два числа в двоичной системе, разделенные на ленте знаком «+».

12. *Составьте программы для машины Тьюринга, которые увеличивают и уменьшают на единицу число, записанное в десятичной системе счисления.

13. Составьте программы для машины Тьюринга, которые выполняют сложение и вычитание двух чисел в десятичной системе счисления.

Практическая работа № 37.
Машина Поста

1. Что делает следующая программа для машины Поста?

Как она будет работать при различных начальных состояниях ленты?

2. Напишите программу для машины Поста, которая неприменима (то есть зацикливается) при любом начальном состоянии ленты.

3. Напишите программу для машины Поста, которая увеличивает на 1 число, записанной в унарной системе счисления. Каретка стоит над первой (самой левой) отметкой.

4. Решите задачу 2 при условии, что в начале работы каретка расположена где-то справа от записи числа.

5. Напишите программу для машины Поста, которая уменьшает на 1 число, записанной в унарной системе счисления. Каретка стоит над первой (самой левой) отметкой.

6. На ленте расставлены метки, между которыми могут быть пропуски длиной в одну ячейку. Заполнить все пропуски метками. Каретка стоит над самой левой меткой.

7. *Напишите программу для машины Поста, которая удваивает число, записанное в единичной системе счисления. Каретка расположена над первой отметкой числа.

8. *Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.

9. *Напишите программу для машины Поста, которая складывает два числа, записанных в унарной системе. Числа расположены на неизвестном расстоянии друг от друга. Каретка находится над левой границей первого (левого) числа.

10. **Напишите программу для машины Поста, которая складывает несколько натуральных чисел. Каждое число кодируется как последовательность расположенных рядом отметок (в унарной системе счисления). Числа отделены друг от друга пробелами. Каретка находится справа от первого числа.

11. **Написать программу для машины Поста, которая находит единственную метку на ленте, которая расположена неизвестно где. Каретка должна остановиться на метке, все другие (временные) метки должны быть стерты. В начале работы каретка расположена над пустой ячейкой.

Практическая работа № 38.
Нормальные алгорифмы Маркова (НАМ)

1. Что делает следующий НАМ, если применить его к символьной цепочке, состоящей из нулей и единиц:

Источник