Машина тьюринга уменьшение числа на 1
Машина Тьюринга: уменьшить заданное число n на 1
Вложения
 | 2.rar (255 байт, 79 просмотров) |
Машина Тьюринга, умножающая число на 11
На ленте машины Тьюринга находится число, записанное в десятичной системе исчисления. Умножьте это.
Машина Тьюринга, умножающая число на 2
На ленте машины Тьюринга находится число, записанное в десятичной системе исчисления. Умножьте это.
Машина Тьюринга: поделить двоичное число с остатком
Дано трехразрядное двоичное число. Осуществить его деление на два с остатком. Число и остаток.
Машина Тьюринга: является ли унарное число степенью трёх
Построить машины Тьюринга для вычисления функций A=< | >. Считая слово P записью числа в.
Вложения
| MT.rar (433 байт, 123 просмотров) |
Для того, чтобы из 099 получить 99, необходимо добавить:
Оставить на ленте то число, которое больше (машина Тьюринга)
Дано два числа, записанных в унарной системе счисления, разделенных пустым символом. Оставить на.
Машина Тьюринга: умножить на 2 число в семеричной системе счисления.
Помогите пожалуйста На ленте машины Тьюринга находится целое положительное число, записанное в.
Машина Тьюринга: увеличить число в семеричной системе счисления на 2.
На ленте машины Тьюринга находится целое положительное число, записанное в семеричной системе.
Машина Тьюринга: оставить на ленте целое число от деления n на 3
Нужно построить функциональную схему Машины тьюринга которая оставляет на ленте целое число от.
Если заданное число больше 3, то увеличить число на 10, иначе уменьшить на 10
Помогите написать программу. Дано число. Если оно больше 3, то увеличить число на 10, иначе.
Уменьшить количество забитых шайб на заданное число, если это число больше 0
Привет. В ячейки K7 появляется общее количество забитых шайб. По нажатию на кнопку надо уменьшить.
Машина тьюринга уменьшение числа на 1
Абстрактные вычислительные машины
Материал взят с ресурса Планета информатики
То есть, всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):
Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние Q2 (команды которого совпадают с командами Q1 предыдущей программы).
Материал взят с ресурса Планета информатики
Решение этой задачи аналогично рассмотренному выше примеру.
Задача 4 (усложнение задачи 3)
Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.
Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.
Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:
Рассмотрим следующие варианты входных слов:
Однако, как ни странно, решение этой задачи вызывает большие трудности. Очень часто ученики строят машину Тьюринга, которая выполняет циклические действия: последовательно пододвигают правые n штрихов к левым.
В этом случае их программа выглядит следующим образом:
На примере этой задачи четко видно, как часто дети пытаются решить задачу уже знакомыми способами. Мне кажется, что, предлагая ученикам задачи на составление машин Тьюринга, мы развиваем способность к нахождению необычных решений, развиваем способность творчески думать!
Эта задача кажется школьникам достаточно легкой, но трудности возникают с остановом машины Тьюринга. Ниже приведен один из возможных вариантов машины Тьюринга для этой задачи.
Идея решения (условие останова). На ленте есть два исходных массива штрихов.
Опишем сначала состояния машины Тьюринга, которые необходимы для решения нашей задачи, а затем составим программу-таблицу.
При решении этой задачи следует обратить внимание на правильное выписывание алфавита:
Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:
После программы запуска возможны варианты:
Практические задания. 1. На ленте машины Тьюринга содержится последовательность символов “+”
1. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.
Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
6. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
7. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
8. Даны два натуральных числа m и n, представленные в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q1обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит сумму чисел m и n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
9. Даны два натуральных числа m и n, представленных в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q1 обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит разность чисел m и n. Известно, что m > n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
10. На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе — “нет”. Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Решения заданий
В состоянии q1 машина ищет правый конец числа, в состоянии q2 — пропускает знак “+”, при достижении конца последовательности — останавливается. В состоянии q3машина знак “+” заменяет на знак “–”, при достижении конца последовательности она останавливается.
Задача 2
Решение этой задачи аналогично рассмотренному выше примеру.
Задача 3
Состояние q1 — уменьшаем младшую (очередную) цифру на 1. Если она не равна нулю, то после уменьшения сразу — останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. В клетку [a0, q1] машина Тьюринга никогда не попадет, поэтому ее можно не заполнять.
Задача 4(усложнение задачи 3)
Состояние q1 — уменьшаем младшую (очередную) цифру на 1. Если она больше 1, то после уменьшения — сразу останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. Если уменьшаемая цифра равна 1, то вместо нее пишем 0 и переходим в состояние q2.
Состояние q2 — после записи “0” в каком-либо разряде надо проанализировать, не является ли этот ноль старшей незначащей цифрой (т.е. не стоит ли слева от него в записи выходного слова a0).
Состояние q3 — если записанный “0” является старшей незначащей цифрой, то его надо удалить из записи выходного слова.
Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.
Задача 5
Состояние q1: если встретили “(”, то сдвиг вправо и переход в состояние q2; если встретили “a0”, то останов.
Состояние q2: анализ символа “(” на парность, в случае парности должны увидеть “)”. Если парная, то возврат влево и переход в состояние q3.
Состояние q3: стираем сначала “(”, затем “)” и переходим в q1.
Задача 6
Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.
Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:
aaa —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
a —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
bbb —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
b —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
ab —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
Результат обсуждения. Машина Тьюринга должна “понимать”, по цепочке каких букв она идет, т.е. у нее должно быть как минимум два состояния. Пусть состояние q1 — движение по цепочке из букв “a”, а q2 — состояние движения по цепочке из букв “b”. Заметим, что цепочка может состоять и из одной буквы. Если мы дошли до конца строки в состоянии q1 или q2, т.е. встретили a0, машина должна остановиться, мы обработали всю строку.
Рассмотрим следующие варианты входных слов:
Результат обсуждения. Первый вариант входного слова можно последовательно обработать следующим образом: bba —> bbb —> вернуться к левому концу цепочки из букв “b” —> abb (заменить первую букву в этой цепочке на “a”). Для выполнения этих действий нам потребуется ввести два новых состояния и, кроме того, уточнить состояние q2. Таким образом, для решения этой задачи нам нужно построить машину Тьюринга со следующими состояниями:
q1 — идем вправо по цепочке букв “a”. Если цепочка заканчивается a0, то переходим вq0; если заканчивается буквой “b”, то переходим в q2;
q2 — идем вправо по цепочке букв “b”, если цепочка заканчивается a0, то переходим вq0; если заканчивается “a”, то заменяем букву “a” на “b”, переходим в состояние q3(цепочку вида 
заменили на цепочку вида 
);
q3 — идем влево по цепочке букв “b” до ее левого конца. Если встретили a0 или “a”, то переходим в q4;
q4 — заменяем “b” на “a” и переходим в q1 (цепочку вида заменяем на цепочку вида 
.
Задача 7
состояние q1 — поиск правой (младшей) цифры числа;
состояние q2—умножение очередной цифры числа на 2 без прибавления 1 переноса;
состояние q3— умножение очередной цифры числа на 2 с прибавлением 1 переноса.
Задача 8
Машина Тьюринга для этой программы выглядит тривиально просто — в ней всего одно состояние. Такая машина Тьюринга выполняет следующие действия: стирает самый правый штрих, ищет разделитель (пустую ячейку) и в эту пустую ячейку помещает штрих, тем самым сформирована непрерывная последовательность штрихов длины n + m.
Однако, как ни странно, решение этой задачи вызывает большие трудности. Очень часто ученики строят машину Тьюринга, которая выполняет циклические действия: последовательно пододвигают правые n штрихов к левым.
В этом случае их программа выглядит следующим образом:
состояние q1 —поиск разделителя;
состояние q2—передвинули штрих;
состояние q3—проверка на конец (все ли штрихи передвинули).
На примере этой задачи четко видно, как часто дети пытаются решить задачу уже знакомыми способами. Мне кажется, что, предлагая ученикам задачи на составление машин Тьюринга, мы развиваем способность к нахождению необычных решений, развиваем способность творчески думать!
Задача 9
Эта задача кажется школьникам достаточно легкой, но трудности возникают с остановом машины Тьюринга. Ниже приведен один из возможных вариантов машины Тьюринга для этой задачи.
Идея решения (условие останова). На ленте есть два исходных массива штрихов.
Штрихи начинаем стирать с левого конца массива m. И поочередно стираем самый левый штрих в массиве m и самый правый штрих в массиве n. Но прежде чем стереть правый штрих в массиве n, проверяем, единственный он (т.е. последний, который надо стереть) или нет.
Опишем сначала состояния машины Тьюринга, которые необходимы для решения нашей задачи, а затем составим программу-таблицу.
Состояние q1 — поиск разделителя между массивами штрихов при движении справа налево;
состояние q2 — поиск левого штриха в массиве m;
состояние q3 — удаление левого штриха в массиве m;
состояние q4 — поиск разделителя при движении слева направо;
состояние q5 — поиск правого штриха в массиве n;
состояние q6 — проверка единственности этого штриха в массиве n, т.е. определяем, был ли он последним;
состояние q7 — если он был последним, то останов, иначе переход на новый цикл выполнения алгоритма.
Задача 10
При решении этой задачи следует обратить внимание на правильное выписывание алфавита:
A = <a0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Д, А, Н, Е, Т>.
Состояние q1—поиск правого конца числа;
состояние q2—анализ младшей цифры числа; если она равна “0” или “5”, т.е. число делится на 5, то переход в состояние q3, иначе переход в состояние q5;
состояние q3—запись буквы “Д” справа от слова на ленте;
состояние q4—запись буквы “А” справа от слова и останов машины;
состояние q5—запись буквы “Н” справа от слова;
состояние q6—запись буквы “Е” справа от слова;
состояние q7—запись буквы “Т” справа от слова и останов машины.