Лабораторная работа № 1
Машина Тьюринга
В каждом варианте лабораторной работы по 5 заданий из приведенного ниже списка.
Задание 1 | Задание 2 | Задание 3 | Задание 4 | Задание 5 | |
Вариант 1 | 1 | 24 | 25 | 41 | 49 |
Вариант 2 | 2 | 23 | 26 | 40 | 50 |
Вариант 3 | 3 | 22 | 27 | 39 | 51 |
Вариант 4 | 4 | 21 | 28 | 38 | 52 |
Вариант 5 | 5 | 20 | 29 | 37 | 53 |
Вариант 6 | 6 | 19 | 30 | 36 | 54 |
Вариант 7 | 7 | 18 | 31 | 35 | 55 |
Вариант 8 | 8 | 17 | 32 | 34 | 56 |
Вариант 9 | 9 | 17 | 25 | 33 | 56 |
Вариант 10 | 10 | 18 | 26 | 48 | 55 |
Вариант 11 | 11 | 19 | 27 | 47 | 54 |
Вариант 12 | 12 | 20 | 28 | 46 | 53 |
Вариант 13 | 13 | 21 | 29 | 45 | 52 |
Вариант 14 | 14 | 22 | 30 | 44 | 50 |
Вариант 15 | 15 | 23 | 31 | 43 | 49 |
Вариант 16 | 16 | 24 | 32 | 42 | 49 |
Вариант 17 | 1 | 24 | 31 | 41 | 50 |
Вариант 18 | 2 | 23 | 30 | 40 | 51 |
Вариант 19 | 3 | 22 | 29 | 39 | 52 |
Вариант 20 | 4 | 21 | 28 | 38 | 53 |
Вариант 21 | 5 | 20 | 27 | 37 | 54 |
Вариант 22 | 6 | 19 | 26 | 36 | 55 |
Вариант 23 | 7 | 18 | 25 | 35 | 53 |
Вариант 24 | 8 | 17 | 26 | 34 | 51 |
Вариант 25 | 9 | 20 | 27 | 33 | 49 |
Во всех заданиях, если не оговорено иное, считать, что в начальный момент времени автомат обозревает крайний левый непустой символ. По окончании программы автомат так же должен обозревать крайний левый непустой символ.
Дано число n в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 3. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в троичной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 2. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в четверичной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 3. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в пятеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 4. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в шестеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 5. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в семеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 3. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в девятеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 6. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в десятичной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 7. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 7. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в троичной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 610. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в четверичной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 410. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в пятеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 3. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в шестеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 4. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в семеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 2. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в девятеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 5. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
Дано число n в десятичной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 4. Составить программу машины Тьюринга в виде таблицы и в виде диаграммы переходов. Описать словами, что выполняется машиной в каждом состоянии.
На информационной ленте машины Тьюринга содержится последовательность символов из алфавита A={0,1,<,>,=}. Построить машину Тьюринга, которая бы заменяла пары символов “ <> ”, на пару “ ! = “. В начальный момент времени автомат обозревает произвольный символ заданной строки. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. Отметьте запрещенные клетки таблицы.
На информационной ленте машины Тьюринга содержится последовательность символов из алфавита A={0,1,!,=}. Построить машину Тьюринга, которая бы заменяла пары символов “!=”, на пару “<>“. В начальный момент времени автомат обозревает произвольный символ заданной строки. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. Отметьте запрещенные клетки таблицы.
На информационной ленте машины Тьюринга содержится непрерывная последовательность символов «|». Сконструируйте машину Тьюринга для замены каждого четвертого символа на «/» (отсчет символов начинается с правого края строки). В начальный момент времени автомат обозревает произвольный символ заданной строки. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
На информационной ленте машины Тьюринга содержится непрерывная последовательность символов «%». Сконструируйте машину Тьюринга для замены каждого третьего символа на «$» (отсчет символов начинается с правого края строки). В начальный момент времени автомат обозревает произвольный символ заданной строки. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
На информационной ленте машины Тьюринга содержится непрерывная последовательность символов «&». Сконструируйте машину Тьюринга для замены каждого пятого символа на «№» (отсчет символов начинается с левого края строки). В начальный момент времени автомат обозревает произвольный символ заданной строки. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
На информационной ленте машины Тьюринга содержится последовательность из открывающих и закрывающих скобок. Построить машину Тьюринга, которая бы удаляла пары взаимных скобок, т. е. расположенных подряд « ( ) ». При удалении символов на их место необходимо записывать два пустых символа. В начальный момент времени автомат обозревает произвольный символ заданной строки символов. В конечный момент времени он должен обозревать крайний правый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
На информационной ленте машины Тьюринга содержится непрерывная последовательность символов «#». Сконструируйте машину Тьюринга для замены каждого второго символа на «@» (отсчет символов начинается с правого края строки). В начальный момент времени автомат обозревает произвольный символ заданной строки. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
На информационной ленте машины Тьюринга содержится непрерывная последовательность символов «*». Сконструируйте машину Тьюринга для замены каждого шестого символа на символ «!» (отсчет символов начинается с левого края строки). В начальный момент времени автомат обозревает произвольный символ заданной строки. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
На информационной ленте машины Тьюринга записано число N (N>2) в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для N = 5. Отметьте запрещенные клетки таблицы. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы.
q1 | q2 | q3 | q4 | q5 | q6 |
| | | q1 R | e q3 L | | q3 L | e q4 R | | q6 S |
e | e q2 L | | q4 R | | q5 L | | q5 L |
На информационной ленте машины Тьюринга записаны два натуральных числа A и B (A>B) в унарной системе счисления, разделенных ровно одной пустой ячейкой. Читающая головка находится напротив крайнего левого символа в записи левого числа. Выполните трассировку программы для некоторых чисел. Отметьте запрещенные клетки таблицы. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу другим способом. Запишите свое решение в виде программы-таблицы.
q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 |
| | e q2 R | | q2 R | | q3 R | e q5 L | | q5 L | | q6 L | | q7 L |
e | e q3 R | e q4 L | | q7 L | e q6 L | e q1 R | e q8 R |
На информационной ленте машины Тьюринга записано натуральное число N в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для N=4. Отметьте запрещенные клетки таблицы. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы.
q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 |
| | | q1 R | e q3 L | e q5 L | e q6 L | | q6 L | e q8 R | |
e | | q2 R | | q3 L | | q4 R | | q4 R | e q7 R |
На информационной ленте машины Тьюринга записано натуральное число в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для некоторого числа. Отметьте запрещенные клетки таблицы. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы.
q1 | q2 | q3 | q4 | q5 | q6 | q7 |
| | 0 q2 R | | q2 R | | q3 R | | q4 L | e q7 R | |
0 | 0 q1 R | | q5 L | ||||
e | | q5 L | e q3 R | | q4 L | e q4 L | e q6 R |
Машина Тьюринга работает с использованием алфавита A={1,+,–}. На информационной ленте записано натуральное число N в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Отметьте запрещенные клетки таблицы. Определите, какую задачу решает, приведенная ниже программа. Выполните ее трассировку для N=4 и N=3. Придумайте свое решение данной задачи и запишите его в табличном виде.
q1 | q2 | q3 | q4 | q5 |
e | e q3 R | e q4 R | + q5 S | – q5 S |
| | e q2 R | e q1 R | ||
+ | ||||
– |
На информационной ленте машины Тьюринга записаны два натуральных числа в унарной системе счисления, разделенных ровно одной пустой ячейкой. Читающая головка находится напротив крайнего левого символа в записи левого числа. Выполните трассировку программы для некоторых чисел. Отметьте запрещенные клетки таблицы. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы.
q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 | q9 |
| | | q1 R | e q2 R | | q4 L | | q4 L | e q6 R | | q6 R | e q8 L | | q8 L |
e | e q2 R | | q3 L | e q3 L | e q5 R | | q7 R | | q7 R | e q9 R |
На информационной ленте машины Тьюринга записано натуральное число N в двоичной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для некоторого числа N=5. Отметьте запрещенные клетки таблицы. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу другим способом. Запишите свое решение в виде программы-таблицы.
q1 | q2 | q3 | q4 |
0 | 1 q1 R | 1 q3 L | |
1 | 0 q1 R | 0 q3 L | |
e | e q2 S | 1 q3 S | e q4 R |
На информационной ленте машины Тьюринга записано число N (N>2) в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для N=6. Отметьте запрещенные клетки таблицы. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы.
q1 | q2 | q3 | q4 | q5 |
| | | q1 R | | q4 L | | q4 L | |
e | e q2 R | | q3 L | | q3 S | e q5 R |
Дано число X в двоичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения двоичного числа на 8, вторая – задачу вычитания 2 из заданного двоичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 8X – 2 и Y2 = (X – 2)*8.
Дано число X в шестнадцатеричной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения шестнадцатеричного числа на 16, вторая – задачу вычитания 3 из заданного шестнадцатеричного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 16X – 3 и Y2 = (X – 3)*16.
Дано число X (X>2) в пятеричной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения пятеричного числа на 25, вторая – задачу вычитания 4 из заданного пятеричного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 25X – 4 и Y2 = (X – 4)*25.
Дано число X в двоичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения двоичного числа на 4, вторая – задачу вычитания 410 из заданного двоичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 4X – 4 и Y2 = (X – 4)*4.
Дано число X (X>2) в четверичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения четверичного числа на 16, вторая – задачу вычитания 3 из заданного четверичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 16X – 3 и Y2 = (X – 3)*16.
Дано число X в троичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения троичного числа на 3, вторая – задачу вычитания 2 из заданного троичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 3X – 2 и Y2 = (X – 2)*3.
Дано число X (X>2) в восьмеричной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения восьмеричного числа на 64, вторая – задачу вычитания 5 из заданного восьмеричного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 64X – 5 и Y2 = (X – 5)*64.
Дано число X в десятичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения десятичного числа на 1000, вторая – задачу вычитания 8 из заданного десятичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 1000X – 8 и Y2 = (X – 8)*1000.
Дано число X в двоичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения двоичного числа на 4, вторая – задачу вычитания 4 из заданного двоичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 4X – 4 и Y2 = (X – 4)*4.
Дано число X в шестнадцатеричной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения шестнадцатеричного числа на 256, вторая – задачу вычитания 13 из заданного шестнадцатеричного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 256X – 13 и Y2 = (X – 13)*256.
Дано число X (X>2) в пятеричной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения пятеричного числа на 5, вторая – задачу вычитания 3 из заданного пятеричного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 5X – 3 и Y2 = (X – 3)*5.
Дано число X в двоичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения двоичного числа на 8, вторая – задачу вычитания 2 из заданного двоичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 8X – 2 и Y2 = (X – 2)*8.
Дано число X (X>2) в четверичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения четверичного числа на 4, вторая – задачу вычитания 2 из заданного четверичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 4X – 2 и Y2 = (X – 2)*4.
Дано число X в троичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения троичного числа на 9, вторая – задачу вычитания 3 из заданного троичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 9X – 3 и Y2 = (X – 3)*9.
Дано число X (X>2) в восьмеричной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения восьмеричного числа на 8, вторая – задачу вычитания 6 из заданного восьмеричного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 8X – 6 и Y2 = (X – 6)*8.
Дано число X в десятичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения десятичного числа на 100, вторая – задачу вычитания 7 из заданного десятичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 100X – 7 и Y2 = (X – 7)*100.
Дано натуральное число X в системе счисления с основанием 8. Написать программу машины Тьюринга для вычисления функции Y(X) = X+1510.
Дано число X в системе счисления с основанием 6. Написать программу машины Тьюринга для вычисления функции Y(X) = X*3.
На ленте машины Тьюринга хранятся несколько унарных числа, разделенных знаками “+”. Написать программу для вычисления суммы этих чисел. В результате на ленте должно остаться одно унарное число, являющееся суммой всех исходных.
Дано унарное число X. Написать программу машины Тьюринга для вычисления функции Y(X) = 3*X.
На информационной ленте машины Тьюринга содержится два числа в унарной системе счисления, разделенных ровно одним пробелом. Сравнить эти два числа и в пустой клетке между числами поставить один из знаков отношения «<», «>», «=». В начальный момент времени автомат обозревает крайний левый символ первого из чисел. В конечный момент времени он должен обозревать символ операции сравнения.
Дано двоичное число, состоящее из 4 цифр. Перевести его в систему счисления с основанием 4. Для решения поставленной задачи создать машину Тьюринга в табличном виде.
Дано четверичное число, состоящее из 6 цифр. Перевести его в систему счисления с основанием 2. Для решения поставленной задачи создать машину Тьюринга в табличном виде.
Дано двоичное число, состоящее из 6 цифр. Поменять местами левую и правую половины числа. Для решения поставленной задачи создать машину Тьюринга в табличном виде.
