а, тьфу! В оригинале же и написано: "В последнем случае при отсутствии редексов просто возвращается исходный терм."

Тогда мне нужно перестать думать, что reduceToNF задумано было как останавливающаяся, когда обнаружен цикл. Наоборот, факт, что оно останавливается на (\x -> x x)(\x -> x x) и есть баг.