Чему равен информационный объем следующего сообщения: Я люблю учиться. Каждый символ кодируется 16 битами.

15*16=240 бит

Объяснение:

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 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Номер 1

использовать Робот

алг

нач

нц пока сверху свободно

вверх

кц

нц пока сверху стена

закрасить

влево

кц

нц пока сверху не стена

влево

кц

нц пока сверху стена

закрасить

влево

кц

вверх

вправо

нц пока снизу стена

закрасить

вправо

кц

нц пока снизу не стена

вправо

кц

нц пока снизу стена

закрасить

вправо

кц

кон

Номер 2

использовать Робот

алг

нач

нц пока сверху стена

закрасить

влево

кц

вправо

нц пока сверху стена

если справа не свободно то

вправо

все

если справа свободно то

вправо

если сверху стена то

закрасить

все

все

кц

влево

нц пока снизу не стена

вниз

кц

нц пока слева не стена и снизу стена

закрасить

влево

кц

кон