Для регистрации в системе необходимо придумать пароль, длиной 12 символ. В качестве символов используются 16 различных заглавных букв. Для хранения каждого пароля отводится минимальное возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объём памяти в байтах, необходимый для хранения 30 таких паролей.

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

// PascalABC.NET 3.1, сборка 1198 от 11.03.2016
begin
  var k:=0;
  var Terminate:boolean;
  repeat
    Terminate:=True;
    var n:=ReadInteger('Введите номер месяца:');
    case n of
    1,3,5,7,8,10,12:Writeln('31 день');
    4,6,9,11:Writeln('30 дней');
    2:Writeln('28 дней в обычном году и 29- в високосном')
    else begin
      Writeln('Вы ошиблись, номер должен быть от 1 до 12');
      Inc(k);
      Terminate:=False
      end
    end
  until Terminate;
  if k>0 then Writeln('Вы ошиблись ',k,' раз(а).')
end.

Тестовое решение:
Введите номер месяца: 18
Вы ошиблись, номер должен быть от 1 до 12
Введите номер месяца: 0
Вы ошиблись, номер должен быть от 1 до 12
Введите номер месяца: 5
31 день
Вы ошиблись 2 раз(а).