О комбинаторах

[arseniiv]

Вот у нас залежалось некоторое множество комбинаторов (которые из серии $\mathrm S$, $\mathrm K$, $\mathrm I$ и пр.). Как определить все подмножества, образующие базис? (Т. е. с помощью комбинаторов из таких подмножеств можно выразить все-все остальные.) Потом можно найти минимальные базисы, которые не являются ничьими надмножествами.

Например, для вышеуказанных трёх минимальный базис только один: $\{\mathrm S,\mathrm K\}$, т. к. $\mathrm I = \mathrm{SKK}$.

Можно почитать о комбинаторах, в частности, в английской Википедии и в русском Викиучебнике.

[Xaositect]

Хм.
Все сложно.
Если учесть изоморфизм Карри-Говарда, то вопрос переформулируется так: какие из указанных истинных формул позитивной интуиционистской логики (тут с термином могу врать, в общем эта та логика, которую этот самый изоморфизм подразумевает) образуют полную систему аксиом для этой самой логики.

И вот я так сходу не могу сказать, а разрешима эта задача вообще или нет.

Да и в изначальной комбинАторной постановке это не очевидно, все-таки Тьюринг-полная штука.

В общем, я тут подумаю, если что еще придумаю - напишу.