ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда.

Простые числа в качестве рисунка, а не фона.

Как же насчет формальной системы для вывода простых чисел? Как это сделать? Способ состоит в том чтобы, не останавливаясь на умножении, обратиться прямо к неделимости, представив ее позитивно. Ниже дана схема аксиом и правило вывода теорем, представляющих понятие числа, не являющегося делителем других чисел (ND = не делитель).

СХЕМА АКСИОМ:  xyNDx, где x и у — строчки тире.

Например, -----ND--, где x заменен на «--» и y — на «---».

ПРАВИЛО: Если xNDy является теорема, то xNDху также будет теоремой.

Приложив это правило дважды, вы можете вывести теорему.

-----ND------------

Которая интерпретируется как «5 не делитель 12». Однако ---ND------ не является теоремой. В чем будет ошибка, если вы попытаетесь вывести эту строчку?

Чтобы определить, что данное число простое, у нас должны быть какие-то сведения о его свойствах неделимости. В частности, мы хотим знать, что это число не делится на 2, 3, 4, и т. д., до числа, меньшего его на единицу. Однако в формальных системах мы не можем позволить себе таких расплывчатых формулировок как «и так далее». Здесь нужна исчерпывающая точность. Нам бы хотелось иметь возможность сказать на языке системы: «число Z свободно от делителей до X» (SOD = свободно от делителей), имея в виду, что не одно число между 2 и X не является делителем Z. Это можно сделать, но здесь есть небольшой трюк. Если хотите, можете попытаться найти его.

Решение заключается в следующем:

ПРАВИЛО: Если --NDz является теоремой, то zSOD-- также будет теоремой.

ПРАВИЛО: Если zSODx и x-NDz являются теоремами, то zSODx также будет теоремой.

Эти два правила, в совокупности, характеризуют понятие свободы от делителей. Все что нам нужно, это указать, что простые числа — это числа, свободные от делителей, включая число на единицу меньшее их самих:

ПРАВИЛО: Если z-SODz является теоремой, то Pz- также будет теоремой.

Не будем забывать, что 2 — тоже простое число!

АКСИОМА: P--

Вот и все, что нам необходимо. Принцип формального выражения «просто-численности» заключается в том, что существует метод проверки, не требующий никакого отступления назад. Вы всегда двигаетесь вперед, проверяя данное число на делимость — сначала на 2, потом на 3, и так далее. Именно эта «монотонность» или однонаправленность — отсутствие игры между укорачивающими и удлиняющими правилами — позволила нам уловить суть простых чисел. И именно этой потенциальной сложностью формальных систем, могущих вместить сколько угодно взаимодействий между движением вперед и назад, объясняются такие ограничивающие результаты как Теорема Гёделя и Проблема Остановки Тюринга, как и тот факт, что не все рекурсивно счетные множества рекурсивны.