Предикат "чётность"

Предикат "чётность" - тоже самое, что функция определяющая чётность. Выходами предиката может быть только 0 (ложь) или 1 (истина).

Предикат "чётность" от множества двоичных чисел

Предварительно см. : Предикатное описание перцептрона.

Данный случай представляет определенный интерес. Если за Х принять, геометрическую фигуру, нарисованную в пространстве R, то предикат "чётность" $\psi (X)$ будет отвечать на вопрос четно ли число точек, образующую фигуру X.

Минский выдвинул теорему:

Теорема 3.1 , (неформальный вариант).  Пусть сетчатка R содержит конечное число точек. Тогда перцептрон не может определить истинность или ложность предиката "число точек в X нечетно", если среди его частных предикатов не найдется ни одного, зависящего от всех точек сетчатки R.

Теорема 3.1.1 , (строгий вариант).  Предикат четность $\psi (X)$ имеет порядок $|R|$. [Другими словами, для вычисления этого предиката требуется, по крайней мере, один частный предикат, носителем которого служит все пространство R.]

Почему эта теорема так важна?

Вот, что Минский писал на этот счет:

0.9.2. Параллельное вычисление. Перцептрон понимался как параллельно действующее устройство в том физическом смысле, что частные предикаты вычисляются одновременно, независимо один от другого. Это оплачивается тем, что необходимо вычислять все частные предикаты, хотя лишь небольшая их часть может фактически иметь отношение к каждому конкретному окончательному решению. Общее количество вычислений может намного превысить то количество, которое должно быть проведено при хорошо организованном последовательном процессе, когда решение о том, что вычислять далее, выносится на основе результата предыдущего вычисления. Поэтому в каждом конкретном случае выбор между параллельным и последовательным методами должен основываться на сопоставлении выигрыша от сокращения времени с затратами на вводимые добавочные вычисления.

Даже предикаты низкого порядка могут потребовать большого количества ненужных вычислений, без которых можно было бы обойтись при последовательном процессе. Соответствующий объем необходимого оборудования может иной раз остаться в пределах физической осуществимости, в особенности если допустима невысокая точность вычислений. Совершенно иное положение в случае перцептронов высокого порядка. Поучительным примером служит предикат "связность", для вычисления этого предиката на тороидальной сетчатке размером 100 X 100 любому перцептрону требуются частные функции, каждая из которых просматривает многие сотни точек! При этом понятие «локальной» функции становится почти неуместным: частные функции сами оказываются глобальными. Кроме того, фантастическое количество возможных частных функций с такими большими носителями гасит любую надежду на то, что полученное путем случайного выбора умеренно большое множество таких функций окажется достаточно плотным, чтобы охватить соответствующее пространство функций. Чтобы уточнить эту мысль, покажем, что для определенных предикатов и классов частных функций количество частных функций, которое нужно использовать (не говоря уже об аппаратуре, реализующей их коэффициенты), непременно превысит границы физической осуществимости.

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