Если ни на одну дробь из набора домножить так, чтобы остаться в натуральных числах, нельзя — программа останавливается.

Понятно, что при этом хорошо заменять числа на их разложения на простые множители — и, например, считать, что чтобы подать на вход программы пару (a,b), нужно взять начальное состояние A=2^a * 3^b, а про результат договориться, что им будет степень пятёрки после остановки.

Например, задача удвоения решается программой из одной дроби: (25/2), тогда из 2^a мы сделаем 5^{2a}.
Задача сложения — дробями (5/2,5/3): начав с
2^a * 3^b, мы получаем 5^{a+b}.

Хорошее упражнение — написать на этом языке "умножение", переводящее 2^a*3^b в 5^{ab}.
А программа, которую написал на доске Конвей, никогда не останавливалась — зато степени двойки, через которые она проходила, были в точности всеми числами вида 2^p, где p — простое.

из всех посвящений Конвею, у XKCD вышло самое поэтичное

На N+1 несколько дней назад вышел наш с Раскиным текст про Конвея —
https://nplus1.ru/material/2020/04/16/on-conway

А ещё коллеги напомнили про текст Конвея и Шипмана про разные доказательства иррациональности корня из 2 —

Вот такой есть текст Конвея и Шипмана про разные доказательства иррациональности корня из 2

И доказательства там обсуждаются действительно разные! Кроме стандартного доказательства с делимостью — вот такое доказательство с наложением квадратов:

Если квадрат со стороной p равен по площади двум квадратам со стороной q, то вот меньшая аналогичная конфигурация: два пустых квадрата со стороной (p-q) по площади равны закрытому дважды квадрату в центре со стороной q-(p-q)=(2q-p).

И если кажется, что такое доказательство применимо только к корню из 2 — то вот такие же рассуждения для корня из трёх и для корня из 5 (точнее, для золотого сечения):

И ещё два классных доказательства.
Аналитическое: пусть корень из 2 рационален. Возведём \sqrt{2}-1 в большую-большую степень. С одной стороны, получаются сколь угодно малые положительные числа. С другой, после раскрытия скобок получаем выражение вида a\sqrt{2}+b, где a и b целые, поэтому она не может быть меньше 1/D, где D — знаменатель корня из двух. Противоречие.

Как легко видеть, оно же показывает, что корень любой степени из любого натурального числа либо натуральный, либо иррациональный — достаточно вычесть целую часть и возводить разность во всё большие степени.

И ещё одно — через обратные: если \sqrt{2}=P/Q, то он же равен 2/\sqrt{2}=2Q/P. Тогда равны их дробные части p/Q=q/P, то есть P/Q=p/q, где p и q меньше. И мы опять запустили процедуру спуска — так что если предположить, что P и Q были наименьшими, то вот и получается противоречие.

И это последнее доказательство — из книги Конвея и Ги, "The Book of Numbers".

Да — если уж я пересказываю эти доказательства, то "доказательство складыванием" тоже симпатичное:

Прикладывание катета к гипотенузе приводит к появлению меньшего треугольника — опять с целыми сторонами.

Да, в трёх доказательствах — folding, переворачивание и квадраты — для корня из двух операция спуска на самом деле одна и та же:
из P и Q делается (2Q-P) и (P-Q).