Задачи для эмулятора Машины Тьюринга (МТ)

Унарная система счисления

Задача 1

Алфавит: 1, λ

Состояния: q0

На ленте записана последовательность из единиц. Каретка находится над одной из цифр последовательности.

Задача: написать алгоритм, перемещающий каретку в ячейку, расположенную непосредственно справа от числа.

Показать решение


q0 1 -> q0 1 R

q0 λ -> q0 λ S

Задача 2

Алфавит: 1, λ

На ленте записана последовательность из единиц (унарная запись числа). Каретка над одной из цифр.

Задача: алгоритм, увеличивающий число на единицу.

Показать решение


q0 1 -> q0 1 R

q0 λ -> q0 1 S

Задача 3

Алфавит: 1, λ

На ленте — унарное число. Каретка над одной из единиц.

Задача: алгоритм, уменьшающий число на единицу.

Показать решение


q0 1 -> q0 1 R

q0 λ -> q1 λ L

q1 1 -> q1 λ S

Задача 4

Алфавит: 1, λ

На ленте — унарное число. Каретка где-то справа от последовательности.

Задача: алгоритм, стирающий число. Машина должна остановиться.

Показать решение


q0 λ -> q0 λ L

q0 1 -> q1 λ L

q1 1 -> q1 λ L

q1 λ -> q1 λ S

Задача 5

Алфавит: 1, λ

На ленте записана последовательность из единиц. Каретка находится где-то справа от последовательности.

Задача: написать алгоритм, перемещающий каретку в начало числа.

Показать решение


q0 1 -> q1 1 L

q0 λ -> q0 λ L

q1 1 -> q1 1 L

q1 λ -> q2 λ R

q2 1 -> q2 1 S

Двоичная система счисления

Задача 6

Алфавит: 0, 1, λ

На ленте — двоичное число. Каретка где-то слева от последовательности.

Задача: переместить каретку к концу числа.

Показать решение


q0 0 -> q1 0 R

q0 1 -> q1 1 R

q0 λ -> q0 λ R

q1 0 -> q1 0 R

q1 1 -> q1 1 R

q1 λ -> q2 λ L

q2 1 -> q2 1 S

q2 0 -> q2 0 S

Задача 7

Алфавит: 0, 1, λ

На ленте — двоичное число. Каретка где-то над последовательностью.

Задача: алгоритм умножения числа на 2.

Показать решение


q0 0 -> q0 0 R

q0 1 -> q0 1 R

q0 λ -> q0 0 S

Задача 8

Алфавит: 0, 1, λ

На ленте — двоичное число. Каретка где-то над последовательностью.

Задача: прибавить 1 в двоичной системе.

Показать решение


q0 0 -> q0 0 R

q0 1 -> q0 1 R

q0 λ -> q1 λ L

q1 0 -> q1 1 S

q1 1 -> q1 0 L

q1 λ -> q1 1 S

Задача 9

Алфавит: 0, 1, λ

На ленте — двоичное число. Каретка где-то над последовательностью.

Задача: вычесть 1 в двоичной системе.

Показать решение


q0 0 -> q0 0 R

q0 1 -> q0 1 R

q0 λ -> q1 λ L

q1 0 -> q1 1 L

q1 1 -> q1 0 S

Задача 10

Алфавит: 0, 1, λ

На ленте — двоичное число. Каретка где-то над последовательностью.

Задача: инвертируйте число, т.е. замените все 0 на 1, а 1 на 0.

Показать решение


q0 0 -> q0 0 R

q0 1 -> q0 1 R

q0 λ -> q1 λ L

q1 0 -> q1 1 L

q1 1 -> q1 0 L

q1 λ -> q1 λ S

Задача 11

Алфавит: 0, 1, λ

На ленте — двоичное число. Каретка где-то над последовательностью.

Задача: инвертируйте число, т.е. замените все 0 на 1, а 1 на 0. Если в результате в числе получились незначащие нули в начале числа, их необходимо стереть.

Показать решение


q0 0 -> q0 0 R

q0 1 -> q0 1 R

q0 λ -> q1 λ L

q1 0 -> q1 1 L

q1 1 -> q1 0 L

q1 λ -> q2 λ R

q2 0 -> q2 λ R

q2 1 -> q2 1 S

q2 λ -> q2 λ S

Троичная система счисления

Задача 12

Алфавит: 0, 1, 2, λ

На ленте — троичное число. Каретка где-то слева от последовательности.

Задача: переместить каретку к концу числа.

Показать решение


q0 λ -> q0 λ R

q0 0 -> q1 0 R

q0 1 -> q1 1 R

q0 2 -> q1 2 R

q1 0 -> q1 0 R

q1 1 -> q1 1 R

q1 2 -> q1 2 R

q1 λ -> q2 λ L

q2 0 -> q2 0 S

q2 1 -> q2 1 S

q2 2 -> q2 2 S

Задача 13

Алфавит: 0, 1, 2, λ

На ленте — троичное число. Каретка где-то над последовательностью.

Задача: увеличить число на 1.

Показать решение


q0 0 -> q0 0 R

q0 1 -> q0 1 R

q0 2 -> q0 2 R

q0 λ -> q1 λ L

q1 0 -> q1 1 S

q1 1 -> q1 2 S

q1 2 -> q1 0 L

q1 λ -> q1 1 S

Задача 14

Алфавит: 0, 1, 2, λ

На ленте — троичное число. Каретка где-то над последовательностью.

Задача: уменьшить число на 1.

Показать решение


q0 0 -> q0 0 R

q0 1 -> q0 1 R

q0 2 -> q0 2 R

q0 λ -> q1 λ L

q1 0 -> q1 2 L

q1 1 -> q1 0 S

q1 2 -> q1 1 S