Меньше чем 3-х основание СС быть не может. (Сама догадайся почему ;-)
Делим:
23 : 3 = 7 ост. 2 — подходит
23 : 4 = 5 ост. 3 — не подходит
23 : 5 = 4 ост. 3 — не подходит
23 : 6 = 3 ост. 5 — не подходит
23 : 7 = 3 ост. 2 — подходит
23 : 8 = 2 ост. 7 — не подходит
23 : 9 = 2 ост. 5 — не подходит
23 : 10 = 2 ост. 3 — не подходит
23 : 11 = 2 ост. 1 — не подходит
23 : 12 = 1 ост. 11 — не подходит
23 : 13 = 1 ост. 10 — не подходит
23 : 14 = 1 ост. 9 — не подходит
23 : 15 = 1 ост. 8 — не подходит
23 : 16 = 1 ост. 7 — не подходит
23 : 17 = 1 ост. 6 — не подходит
23 : 18 = 1 ост. 5 — не подходит
23 : 19 = 1 ост. 4 — не подходит
23 : 20 = 1 ост. 3 — не подходит
23 : 21 = 1 ост. 2 — подходит
23 : 22 = 1 ост. 1 — не подходит
23 : 23 = 1 ост. 0 — не подходит
Далее для всех СС больше 23 остаток будет 23. Следовательно нет смысла их рассматривать.
Итого: 2, 7 и 21.
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 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
1321
Объяснение:
Число 2^900 в двоичном виде - это единица с девятьюстами нулями.
Число 7 - это 2^2+2^1+2^0
2^900-2^0=2^900-1=2^899 (в двоичном виде - это 900 единиц)
2^2+2+1 в двоичном виде выглядит как 110.
Операция 2^899-2^2-2^1 в двоичном виде представляет из себя замену предпоследних, 898-й и 899-й единиц на 0. Число в двоичном виде будет выглядеть как 897 единиц, затем два нуля, затем единица.
Значащих нулей в числе 2^900-7 рано двум.
8^740=(2^3)^740=2^(740*3)=2^2220
Число 2^2220 в двоичном виде - это единица с двумя тысячами двести двадцатью нулями.
2220-900+1=1321 То есть при сложении, число 2^900-7 записывается в числе 2^2220 начиная с 1321-го разряда.
Искомое число 8^740+2^900-7 в двоичном виде будет выглядеть как единица, 1319 нулей, 897 единиц, два нуля и одна единица.
Число значащих нулей в этом числе составит 1319+2=1321.