Я – странная петля. Дуглас Хофштадтер

Чтение книги онлайн.

      Давайте представим, что у Доминониума есть некий числовой «ввод». Мы берем интересующее нас натуральное число – допустим, 641 – и выставляем ровно столько костей, одну к другой, в «зарезервированном» участке цепи. Теперь мы толкаем первую костяшку Доминониума, после чего запускается цепочка событий Руба Голдберга: кость падает за костью, и вскоре вся 641 кость входного участка цепи упадет, запустив разные циклы, один из которых, предположим, проверяет делимость входного числа на 2, другой на 3, и так далее. Если хотя бы один делитель найден, в определенный участок цепи – назовем его «участок делимости» – посылается сигнал, и если мы видим, что кости на этом участке упали, мы понимаем, что у введенного числа есть делители и, следовательно, оно не простое. И наоборот, если введенное число не имеет делителей, участок делимости никогда не будет запущен и мы поймем, что число простое.