Логические операции без сравнений

Вместо того, чтобы сразу браться за задачу о Тьюринг-полноте целиком, сначала посмотрим, можно ли изготовить логическую операцию «и» пригодной для процессора без команд. Наиболее известная реализация данной операции без явных сравнений содержится в синтаксическом сахаре λ-исчисления:

True = λx.λy.x;
False = λx.λy.y;
And = λp.λq.p q p.

Вот пример вычисления:

And True False = (λp.λq.p q p) True False → True False True = (λx.λy.x) False True → False.

Почему истина и ложь выбраны таким образом? Ответ на этот вопрос лежит в их обобщении — комбинаторах, которые выбирают из списка

<M₀, M₁, … , M_n> = λx.x M₀ M₁ … M_n

i-ый элемент. Такие комбинаторы выглядят следующим образом:

P_{i, n} = λp.p (λx₀.λx₁…λx_n.x_i).

Но применить подобные функции-проекции к спискам мы можем и без всяких условных переходов, натуральных чисел, арифметических или логических операций, а использовав вместо них исключительно разыменование и копирование указателей в памяти:

void **case = (void **)NULL[0];
void **case0 = (void **)case[0];
void **case1 = (void **)case[1];

void **cond = (void **)NULL[1];
void **cond0 = (void **)cond[0];
void **cond1 = (void **)cond[1];

void **result = (void **)cond0[1];

cond0[0] = case0;
cond1[0] = case1;

Истинностное значение cond здесь предполагается в виде {X, Y}, где либо X[1] = X в случае истины, либо X[1] = Y — в противном случае. Поэтому результат окажется по адресу result[0] и будет равен либо case0, либо case1 для истины и лжи, соответственно. С учетом данных конструкций, читателю уже не должно казаться таким сложным

Упражнение. Построить логические «и», «или» и «не» или показать, что это невозможно.