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 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Наивные - загадываем число. Прибавляем к нему 7. Отнимаем загаданное число. x + 7 - x = 7 - загадываем число. Умножаем его на 7. Делим на загаданное число (не сработает для нуля) x * 7 / x = 7
Можно немного это замаскировать: - загадываем число. Умножаем его на 15873. Прибавляем 111111. Делим на 15873. отнимаем загаданное число. (15873x + 111111)/15873 - x = 7
Можно использовать какой-нибудь фокус, например, складывание сумм цифр до тех пор, пока не получится одно число (т.н. "числовой корень", пример: 255 -> 2 + 5 + 5 = 12 -> 1 + 2 = 3) - загадываем натуральное число. Умножаем на 9, находим числовой корень. Отнимаем 2. Разгадка в том, что числовой корень любого числа, делящегося на 9 и не равного нулю, равен 9.
Маскировка: - загадываем натуральное число. Умножаем на 777 и находим числовой корень. Потом на 666 и находим числовой корень. Прибавляем к результату 666. Находим сумму кубов цифр результата. И еще раз. Смотрим на число сотен результата. 666 делится на 9, так что числовой корень числа (666 * что-то) равен 9. 666 + 9 = 675. 6^3 + 7^3 +5^3 = 684. 6^3 + 8^3 + 4^3 = 792
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 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
- загадываем число. Прибавляем к нему 7. Отнимаем загаданное число.
x + 7 - x = 7
- загадываем число. Умножаем его на 7. Делим на загаданное число (не сработает для нуля)
x * 7 / x = 7
Можно немного это замаскировать:
- загадываем число. Умножаем его на 15873. Прибавляем 111111. Делим на 15873. отнимаем загаданное число.
(15873x + 111111)/15873 - x = 7
Можно использовать какой-нибудь фокус, например, складывание сумм цифр до тех пор, пока не получится одно число (т.н. "числовой корень", пример: 255 -> 2 + 5 + 5 = 12 -> 1 + 2 = 3)
- загадываем натуральное число. Умножаем на 9, находим числовой корень. Отнимаем 2.
Разгадка в том, что числовой корень любого числа, делящегося на 9 и не равного нулю, равен 9.
Маскировка:
- загадываем натуральное число. Умножаем на 777 и находим числовой корень. Потом на 666 и находим числовой корень. Прибавляем к результату 666. Находим сумму кубов цифр результата. И еще раз. Смотрим на число сотен результата.
666 делится на 9, так что числовой корень числа (666 * что-то) равен 9. 666 + 9 = 675. 6^3 + 7^3 +5^3 = 684. 6^3 + 8^3 + 4^3 = 792