Тред №243789

С обещанным доказательством вышел облом. Впрочем, отрицательный результат -- тоже результат, если речь идёт об исследовании. Похоже, сдвиговые регистры с классическими (XOR'овыми) обратными связями не образуют полного базиса. Идея была такая: известно, что базис дают NAND или NOR. Ну, инверсию сделать несложно, поэтому достаточно реализовать для последовательно введённых двух аргументов AND или OR для формального доказательства того, что на таком железе можно проводить любые вычисления в рамках булевой алгебры. Так вот, это, видимо, невозможно. В любом бите регистра количество единиц или нулей всегда чётное (если смотреть по всем комбинациям аргументов), от числа и характера обратных связей это не зависит.

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