Машина Тьюринга

Машина Тьюринга

11 класс

Машина Тьюринга — это автомат, который управляется таблицей

Возможные состояния:

Алгоритм:

Задача 1.

Пусть A={0, 1, _}. На ленте в ячейках находятся символы из алфавита в следующем порядке 0011011. каретка находится над первым символом. Необходимо составить программу, которая заменит 0 на 1, 1 на 0 и вернет каретку в первоначальное положение.

Задача 2.

Дано: конечная последовательность 0 и 1 (001101011101). Необходимо выписать их после данной последовательности, через пустую ячейку, а в данной последовательности заменить их на 0.

Например:

Из 001101011101

получим 000000000000 1111111

На ленте МТ находится натуральное число N. Разработать алгоритм машины Тьюринга, который бы умножил заданное число на 2