p/2, если p четно,

(Зp + 1)/2, если p нечетно,

Это вычеркивает некоторые члены предыдущей последовательности, не меняя проблемы остановки:

7 11 17 26 13 90 10 5 8 4 2 1

Вы можете пойти еще дальше в том же направлении, объединяя вместе все последовательные шаги, действующие по правилу (Зp + 1)/2, и все следующие за ними шаги, состоящие в делении на два. Вы получите два новых правила перехода, гораздо более уплотненные. Свяжите их и пустите в ход. Для числа 7 вы должны без задержки получить последовательность

7 13 5 1

Это позволяет рассматривать обобщения задачи. Пусть k — нечетное число. Возьмем в качестве правил перехода следующие:

p/2, если p четно,

k * p + k– 2, если p нечетно.

Возможно уплотнение, аналогичное предыдущему. Для k = 5 следующее за числом 3 есть 3, и существуют исходные точки, для которых программа не останавливается. Для k = 7 она идет точно так же. Так что проблема остановки связана со свойством числа k. Я бы здесь… Впрочем, мало ли чего я хочу!

Это — класс самых разнообразных задач. Задаются точные арифметические операции, в которых некоторые цифры либо стерты, либо заменены буквами. В данной операции одна и та же буква всегда заменяет одну и ту же цифру, и разные буквы представляют поэтому разные цифры. Нужно восстановить исходную операцию. Есть случаи, в которых это сводится к решению системы уравнений с неизвестными, представляющими собой букву, — системы, решение которой дает также решение исходной задачи. Компьютер не видит ничего скрытного. Таким образом, если что-то не так, то нужно действовать систематически методом проб и ошибок. Нужно выбрать значения для одних букв и получить с их помощью значения остальных. Нужно проверить, что разным буквам соответствуют разные значения. После конечного числа попыток мы получим решение — если оно единственно — или список всех возможных решений. А еще существуют промежуточные решения: вычисление ограничивает число осуществляемых попыток.

Головоломка 8. SEND MORE MONEY. [4]

Это — лаконичная телеграмма английского студента своему отцу. История умалчивает о том, как отец это принял и были ли отправлены деньги…

SEND + MORE = MONEY

Программа очень легкая. Время вычисления короткое. Едва ли это головоломка. Как раз для тренировки…

Головоломка 9. HELP THE YOUNG. [5]

Конечно, конечно. Почему бы не послать им еще денег? Та же задача:

HELP + THE = YOUNG

Отметим разницу с предыдущей задачей. Предыдущая использовала не все цифры от 0 до 9. В этой участвуют все. Можете ли вы воспользоваться этим?

DEVOIR, LECON, 'EL`EVE. [6]

Есть аналогичные зашифрованные сложения по-французски. Например, такая:

'EL`EVE + LECON = DEVOIR

? Головоломка 10. Зашифрованное умножение.

Довольно сложений, это становится скучным. Вот зашифрованное умножение:

ABCDE * 9 = FGHIJ

Здесь 10 букв представляют 10 различных цифр, так что одна из них равна 9. Можно сразу кое-что сказать о возможных значениях букв, но чтобы получить решение, придется идти буквально ощупью. Столько же придется искать и компьютеру.

?* Головоломка 11. Забавное число.

Число 123456789 обладает забавными свойствами:

123456789 * 2 = 246913578

Как и исходное, удвоенное число образовано всеми девятью цифрами, кроме 0.

123456789 * 4 = 493827156

Результат снова образован девятью цифрами, отличными от 0.

123456789 * 5 = 617283945

По-прежнему 9 цифр.

123456789 * 7 = 864197523

Опять 9 цифр, и это еще не все.

123456789 * 8 = 987654312

Но это не работает ни для 3, ни для 6. Это не может работать и для 9, потому что в результате больше 9 цифр,

Тем не менее есть много чисел, образованных всеми 9 цифрами (кроме 0), которые после умножения на 3 дают результат, образованный теми же девятью цифрами. Можете ли вы дать список всех таких чисел, оканчивающихся на 9? И также список тех, которые кончаются на 3?

Можно ли распространить использованный метод на случай умножения на 6?

Компьютер можно использовать для доказательства теорем. Это — трудная задача искусственного интеллекта. Мы снабжаем компьютер правилами вывода, даем формулировку того, что требуется доказать, и исходные аксиомы. Компьютер пытается найти последовательность правил вывода, которые могут привести от исходных данных к требуемым рёзультатам.