On the Convergence of Tsetlin Machines for the AND and the OR Operators

## Abstract

Abstract The Tsetlin Machine (TM) is a novel machine learning algorithm based on propositional logic, which has obtained the state-of-the-art performance on several pattern recognition problems. In previous studies, the convergence properties of TM for 1-bit operation and XOR operation have been analyzed. To make the analyses on the basic digital operations complete, in this article, we analyze the convergence when input training samples follow AND and OR operators respectively. Our analyses reveal that the TM can converge almost surely to reproduce AND and OR operators, which are learnt from training data over an infinite time horizon. Specifically, by analysing the OR operator, we reveal the convergence property of TM when two sub-patterns can be jointly represented by one clause, which is quite distinct compared with the analysis of the XOR case.
The analyses on AND and OR operators, together with the previously analysed 1-bit and XOR operations, complete the convergence analyses on basic operators in Boolean algebra.

###### Index Terms:

## 1 Introduction

The Tsetlin Machine (TM) [] organizes groups of Tsetlin Automata (TAs) [] to collaboratively learn distinct patterns in training data. A TA, which is the core learning entity of TM, is a kind of learning automata that select their current actions based on past experiences learnt from the environment in order to obtain the maximum reward. The state of the art of the study in learning automate is presented in [, ]. In TM, each group of TAs builds a clause in propositional logic, which captures a specific sub-pattern. Specifically, a clause is a conjunction of literals, where a literal is a propositional input or its negation. Once distinct sub-patterns are learnt by a number of clauses, the overall pattern recognition task is completed by a voting scheme from the clauses.

TMs possess two main advantages: transparent inference and hardware friendliness []. TMs provide transparent learning that shows how sub-patterns are composed in clauses, by including or excluding certain literals based on the feedback that they receive. Employing propositional logic for knowledge representation provides rules rather than a mathematical computation, which is advantageous compared with computation based approaches, such as deep learning. In fact, for the deep learning based models, such as attention mechanisms, the learning process itself remains inside a black-box neural network. In general, attention weights do not provide a meaningful explanation [, ]. Unlike neural networks, the propositional form of TMs, with non-monotone clauses, is human-interpretable []. Computationally, TMs is composed by a set of finite-state automata that are in nature appropriate for hardware implementation []. Different from the comprehensive arithmetic operations required by most other AI algorithms, only increment and decrement operations are sufficient for a TA in TM to learn [], which is indeed hardware friendly.

There are many variations of TMs with two main architectures: the convolutional TM (CTM) [] and the regression TM (RTM) [, ]. The TM, together with its variations, has been employed in several applications, such as word sense disambiguation [], aspect-based sentiment analysis [], novelty detection [], text classification [] with enhanced interpretability [], and solving contextual bandit problems []. The CUDA version of TM [] is also developed, which makes the TM notably more applicable by speeding up TM learning through a novel parallelization scheme, where each clause runs and learns independently in its own thread. The above studies indicate that TMs obtain better or competitive classification and regression accuracy compared with most of the state-of-the-art techniques. At the same time, the transparency of learning is maintained with smaller memory footprint and higher computational efficiency.

For the convergence analysis of TM, the convergence properties of the 1-bit operator and the XOR operator have been analyzed in [] and [] respectively. In more details, the convergence for unary operators on one-bit data, i.e., the IDENTITY- and the NOT operators, is analyzed in [], where we first prove that the TM can converge almost surely to the intended pattern when the training data is noise-free. Thereafter, we analyze the effect of noise, establishing how the noise in the data and the granularity parameter of the TM, $s$, govern convergence []. Through the study of the 1-bit case, the functionalities of the hyper-parameter $s$ for granularity of learning and the chain length of the TA are thoroughly revealed. The convergence property of XOR operator is studied in []. For XOR operator, there are two sub-patterns, namely (0, 1) and (1, 0), with non-linear relationship. We first prove the convergence of a simple structure with two clauses, each of which has four TAs with two states. Markov chain analysis is adopted for that proof. The analysis indicates that even that simple structure can guarantee the TM to learn the intended XOR logic almost surely. Thereafter, we study the convergence behavior of a more general case, where multiple clauses exist. Through the latter analysis, we reveal the crucial role the hyper-parameter $T$ plays in TM, showing how this hyper-parameter balances the clauses to robustly capture distinct sub-patterns within one class.

Paper Contributions. Based on the summary of the existing analytical work of TM, we understand that
the convergence study of the basic logic operators is not complete. In this paper, we will fill in the gap and analyze the convergence of TM for AND and OR operators.
This paper, together with [] and [], completes the study on the convergence analysis of all fundamental Boolean operators in TM, offering a conclusive convergence analysis and establishing a milestone of TM studies. Additionally, because the OR operator offers the possibility
to jointly represent two sub-patterns by one clause, the convergence analysis of the OR operator is quite different compared with the XOR case, which adds new insights to the convergence nature of the TM.

Paper Organization. The remaining of the paper is organized as follows. Section [2](#S2) briefly reviews the TM and specifies the training process. In Section [3](#S3), we present our analytical procedure and the main analytical results for the AND operator. Section [4](#S4) analyzes the convergence for the OR operator before we conclude the paper in Section [5](#S5).

## 2 Brief Overview of the TM

To make the article self-contained, we present the basics of TM here in this section. Note that this section is technically identical to Section 2 of article []. Those who already are familiar with the concept and notations of TM can jump directly to Section [3](#S3).

### 2.1 Review of Tsetlin Machines

A TM that is to learn the characteristics of class $i$ is formed by $m$ teams of TAs. More specifically, the TM trains TAs to formulate $m$ clauses (TA teams), $C^{i}_{j},~{}j=1,2,...,m$, and to capture the sub-patterns that characterize the class $i$. The input of a TM is denoted by $\mathbb{X}=[x_{1},x_{2},\ldots,x_{o}]$, $x_{k}\in\{0,1\}$, $k=1,2,\ldots,o$. Each TA team contains $o$ pairs of TAs, and thus a TA team $\mathcal{G}^{i}_{j}=\{\mathrm{TA}^{i,j}_{k^{\prime}}|1\leq k^{\prime}\leq 2o\}$ has $2o$ TAs. For a certain input variable $x_{k}$, there is a pair of TAs that are responsible for its role in the clause. The automaton $\mathrm{TA}^{i,j}_{2k-1}$ is responsible for the original form of the input $x_{k}$, whereas $\mathrm{TA}^{i,j}_{2k}$ addresses the negation of $x_{k}$, i.e., $\neg x_{k}$. Note that the original forms of the inputs and their negations are jointly referred to as literals.

Figure: Figure 1: A two-action Tsetlin automaton with $2N$ states [].

Figure: Figure 2: A TA team $G^{i}_{j}$ consisting of $2o$ TAs []. Here $I(x_{1})$ means “include $x_{1}$” and $E(x_{1})$ means “exclude $x_{1}$”.

Figure: Figure 3: TM voting architecture [].

Each TA chooses one of two actions, i.e., it either “Includes” or “Excludes” its literal. Figure [1](#S2.F1) illustrates the structure of a TA with two actions. When the TA is in any state on the left-hand side, i.e., 0 0 to $N-1$, the action “Include” is selected. The action becomes “Exclude” when the TA is in a state on the right-hand side. The transitions among the states are triggered by a reward or a penalty that the TA receives from the environment, which, in this case, is determined by different types of feedback defined in the TM (to be explained later). Collectively, the outputs of the TA team take part in a conjunction, expressed by the conjunctive clause []:

$$ $C^{i}_{j}(\mathbb{X})=\begin{cases}\left(\bigwedge\limits_{k\in I^{i}_{j}}{x_{k}}\right)\wedge\left(\bigwedge\limits_{k\in\bar{I}^{i}_{j}}{\neg x_{k}}\right)\wedge 1&\mathrm{for\ training},\\ \left(\left(\bigwedge\limits_{k\in I^{i}_{j}}{x_{k}}\right)\wedge\left(\bigwedge\limits_{k\in\bar{I}^{i}_{j}}{\neg x_{k}}\right)\right)\vee 0&\mathrm{for\ testing}.\end{cases}$ (1) $$

In Eq. ([1](#S2.E1)), $I^{i}_{j}$ and $\bar{I}^{i}_{j}$ are the subsets of indexes for the literals that have been included in the clause. $I^{i}_{j}$ contains the indexes of included original (non-negated) inputs, $x_{k}$, whereas $\bar{I}^{i}_{j}$ contains the indexes of included negated inputs, $\neg x_{k}$. The “0” and “1” in Eq. ([1](#S2.E1)) make sure that $C^{i}_{j}(\mathbb{X})$ also is defined when all the TAs choose to exclude their literals. As can be observed, during training, an “empty” clause outputs $1$, while it outputs 0 0 during testing and operation.

Figure [2](#S2.F2) illustrates the structure of a clause and its relationship to its literals. Here, for ease of notation in the analysis of the training procedure, let $I(x)=x,~{}I(\neg x)=\neg x$, and $E(x)=E(\neg x)=1$, with the latter meaning that an excluded literal does not contribute to the output.

Multiple clauses, i.e., the TA teams in conjunctive form, are assembled into a complete TM. There are two architectures for clause assembling: Disjunctive Normal Form Architecture and Voting Architecture. In this study, we focus on the latter one,
as shown in Figure [3](#S2.F3). The voting consists of summing the outputs of the clauses:

$$ $f_{\sum}(\mathcal{C}^{i}(\mathbb{X}))=\sum^{m}\limits_{j=1}C_{j}^{i}(\mathbb{X}).$ (2) $$

The output of the TM, in turn, is decided by the unit step function:

$$ $\displaystyle\hat{y}^{i}={\begin{cases}\mbox{{0}}&{\text{for }}f_{\sum}(\mathcal{C}^{i}(\mathbb{X}))<Th\\ \mbox{{1}}&{\text{for }}f_{\sum}(\mathcal{C}^{i}(\mathbb{X}))\geq Th\end{cases}},$ (3) $$

where $Th$ is a predefined threshold for classification. Note that for voting architecture, the TM can assign a polarity to each TA team []. For example, TA teams with odd indexes possess positive polarity, and they vote for class $i$. The remaining TA teams have negative polarity and vote against class $i$. The voting consists of summing the output of the clauses, according to polarity, and the threshold $Th$ is configured as zero. In this study, for ease of analysis, we consider only positive polarity clauses. Nevertheless, this does not change the nature of TM learning.

### 2.2 The Tsetlin Machine for Learning Patterns

#### 2.2.1 The Tsetlin Machine Game

The training process is built on letting all the TAs take part in a decentralized game. Training data $(\mathbb{X}=[x_{1},x_{2},...,x_{o}],~{}y^{i})$ is obtained from a data set $\mathcal{S}$, distributed according to the probability distribution $P(\mathbb{X},y^{i})$. In the game, each TA is guided by Type I Feedback and Type II Feedback defined in Table [I](#S2.T1) and Table [II](#S2.T2), respectively. Type I Feedback is triggered when the training sample has a positive label, i.e., $y^{i}=1$, meaning that the sample belongs to class $i$. When the training sample is labeled as not belonging to class $i$, i.e., $y^{i}=0$, Type II Feedback is utilized for generating responses. The parameter, $s$, controls the granularity of the clauses and a larger $s$ encourages more literals to be included in each clause. A more detailed analysis on parameter $s$ can be found in [].

**TABLE I: Type I Feedback — Feedback upon receiving a sample with label $y=1$, for a single TA to decide whether to Include or Exclude a given literal $x_{k}/\neg x_{k}$ into $C^{i}_{j}$. NA means not applicable [].**
| Value of the clause $C^{i}_{j}(\mathbb{X})$ | 1 | 0 |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Value of the Literal $x_{k}$/$\lnot x_{k}$ | 1 | 0 | 1 | 0 |  |
| Include Literal | $P(\mathrm{Reward})$ | $\frac{s-1}{s}$ | NA | 0 0 | 0 0 |
| $P(\mathrm{Inaction})$ | $\frac{1}{s}$ | NA | $\frac{s-1}{s}$ | $\frac{s-1}{s}$ |  |
| $P(\mathrm{Penalty})$ | 0 0 | NA | $\frac{1}{s}$ | $\frac{1}{s}$ |  |
| Exclude Literal | $P(\mathrm{Reward})$ | 0 0 | $\frac{1}{s}$ | $\frac{1}{s}$ | $\frac{1}{s}$ |
| $P(\mathrm{Inaction})$ | $\frac{1}{s}$ | $\frac{s-1}{s}$ | $\frac{s-1}{s}$ | $\frac{s-1}{s}$ |  |
| $P(\mathrm{Penalty})$ | $\frac{s-1}{s}$ | 0 0 | 0 0 | 0 0 |  |

**TABLE II: Type II Feedback — Feedback upon receiving a sample with label $y=0$, for a single TA to decide whether to Include or Exclude a given literal $x_{k}/\neg x_{k}$ into $C^{i}_{j}$. NA means not applicable [].**
| Value of the clause $C^{i}_{j}(\mathbb{X})$ | 1 | 0 |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Value of the Literal $x_{k}/\neg x_{k}$ | 1 | 0 | 1 | 0 |  |
| Include Literal | $P(\mathrm{Reward})$ | 0 0 | $\mathrm{NA}$ | 0 0 | 0 0 |
| $P(\mathrm{Inaction})$ | $1.0$ | $\mathrm{NA}$ | $1.0$ | $1.0$ |  |
| $P(\mathrm{Penalty})$ | 0 0 | $\mathrm{NA}$ | 0 0 | 0 0 |  |
| Exclude Literal | $P(\mathrm{Reward})$ | 0 0 | 0 0 | 0 0 | 0 0 |
| $P(\mathrm{Inaction})$ | $1.0$ | 0 0 | $1.0$ | $1.0$ |  |
| $P(\mathrm{Penalty})$ | 0 0 | $1.0$ | 0 0 | 0 0 |  |

To avoid the situation that a majority of the TA teams learn only a small subset of the sub-patterns in the training data, forming an incomplete representation, we use a parameter $T$ as target for the summation $f_{\sum}$. If the votes for a certain sub-pattern already reach a total of $T$ or more, neither rewards nor penalties are provided to the TAs when more training samples of this particular sub-pattern are given. In this way, we can ensure that each specific sub-pattern can be captured by a limited number, i.e., $T$, of available clauses, allowing sparse sub-pattern representations among competing sub-patterns. In more details, the strategy works as follows:

Generating Type I Feedback. If the output from the training sample $\mathbb{X}$ is $y^{i}=\mbox{{1}}$, we generate, in probability, *Type I Feedback* for each clause $C^{i}_{j}\in\mathcal{C}^{i}$, where $\mathcal{C}^{i}$ is the set of clauses that are trained for class $i$. The probability of generating Type I Feedback is []:

$$ $u_{1}=\frac{T-\mathrm{max}(-T,\mathrm{min}(T,f_{\sum}(\mathcal{C}^{i}(\mathbb{X}))))}{2T}.$ (4) $$

Generating Type II Feedback.
If the output of the training sample $\mathbb{X}$ is $y^{i}=\mbox{{0}}$, we generate, again, in probability, *Type II Feedback* to each clause $C^{i}_{j}\in\mathcal{C}^{i}$. The probability is []:

$$ $u_{2}=\frac{T+\mathrm{max}(-T,\mathrm{min}(T,f_{\sum}(\mathcal{C}^{i}(\mathbb{X}))))}{2T}.$ (5) $$

After Type I Feedback or Type II Feedback is generated for a clause, the individual TA within each clause is given reward/penalty/inaction according to the probability defined, and then the states of the corresponding TAs are updated.

## 3 Convergence Analysis of TM for the AND Operator

In this section, we will prove the convergence of the AND operator. In this proof, we assume that the training samples do not have any noise, i.e.,

$$ $\displaystyle P\left(y=1|x_{1}=1,x_{2}=1\right)=1,$ (6) $\displaystyle P\left(y=0|x_{1}=0,x_{2}=1\right)=1,$ $\displaystyle P\left(y=0|x_{1}=1,x_{2}=0\right)=1,$ $\displaystyle P\left(y=0|x_{1}=0,x_{2}=0\right)=1.$ $$

We also assume that in the training samples, the above four cases will appear with non-zero probability. This means that all of the four types of training samples will appear during the training process.

Because the considered AND operator has only one pattern of input $\mathbb{X}$ that will trigger true output, we employ just one clause in this TM. Because the considered TM has only one clause, for ease of expression, we ignore the indices of the classes and the clauses in our notation in the remainder of the proof. After simplification, $\mathrm{TA}^{i,j}_{k}$ becomes $\mathrm{TA}_{k}$, and $C_{1}^{1}$ becomes $C$. Since there are two input parameters, we configure 4 TAs, namely, $\mathrm{TA}_{1}$, $\mathrm{TA}_{2}$, $\mathrm{TA}_{3}$, and $\mathrm{TA}_{4}$. $\mathrm{TA}_{1}$ has two actions, i.e., including or excluding $x_{1}$. Similarly, $\mathrm{TA}_{2}$ corresponds to including or excluding $\neg x_{1}$. $\mathrm{TA}_{3}$ and $\mathrm{TA}_{4}$ determine the behavior of the $x_{2}$ and $\neg x_{2}$, respectively.

Clearly, there is only one pattern that will trigger the output $y$ to be $1$, i.e., $x_{1}=1,x_{2}=1$, which corresponds to the logic to both include $x_{1}$ and $x_{2}$, and to both exclude $\neg x_{1}$ and $\neg x_{2}$ after training. Therefore, once the TM can converge correctly to the intended operation, the actions of $\mathrm{TA}_{1}$, $\mathrm{TA}_{2}$, $\mathrm{TA}_{3}$, and $\mathrm{TA}_{4}$ should be(^1^11We use “I” and “E” as abbreviations for include and exclude respectively.) I, E, I, and E.

To analyze the convergence of TM in the training process, we freeze the transition of the two TAs for the first bit of the input and study behavior of the second bit of input. Clearly, there are four possibilities for the first bit, $x_{1}$, as:

- •
Case 1: $\mathrm{TA}_{1}=\text{E}$, $\mathrm{TA}_{2}=\text{I}$, i.e., include $\neg x_{1}$.
- •
Case 2: $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{E}$, i.e., include $x_{1}$.
- •
Case 3: $\mathrm{TA}_{1}=\text{E}$, $\mathrm{TA}_{2}=\text{E}$, i.e., exclude both $x_{1}$ and $\neg x_{1}$.
- •
Case 4: $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{I}$, i.e., include both $x_{1}$ and $\neg x_{1}$.

In the next subsections, we will analyze the behavior of the TAs for the second bit with different input training samples, given the above four distinct cases of $x_{1}$, respectively.

### 3.1 Case 1: Include ¬ x 1 subscript 𝑥 1 \neg x_{1}

In this subsection, we assume that the TAs for first bit is frozen as $\mathrm{TA}_{1}=\text{E}$ and $\mathrm{TA}_{2}=\text{I}$, and thus the overall joint action for the first bit is “$\neg x_{1}$”. In this case, we have 4 situations to study, detailed below:

- 1.
We study the transition of $\mathrm{TA}_{3}$ when it has “Include” as its current action, given different actions of $\mathrm{TA}_{4}$ (i.e., when the action of $\mathrm{TA}_{4}$ is frozen as “Include” or “Exclude”.).
- 2.
We study the transition of $\mathrm{TA}_{3}$ when it has “Exclude” as its current action, given different actions of $\mathrm{TA}_{4}$ (i.e., when the action of $\mathrm{TA}_{4}$ is frozen as “Include” or “Exclude”.).
- 3.
We study the transition of $\mathrm{TA}_{4}$ when it has “Include” as its current action, given different actions of $\mathrm{TA}_{3}$ (i.e., when the action of $\mathrm{TA}_{3}$ is frozen as “Include” or “Exclude”.).
- 4.
We study the transition of $\mathrm{TA}_{4}$ when it has “Exclude” as its current action, given different actions of $\mathrm{TA}_{3}$ (i.e., when the action of $\mathrm{TA}_{3}$ is frozen as “Include” or “Exclude”.).

In what follows, we will go through, exhaustively, the four situations.

#### 3.1.1 Study TA 3 subscript TA 3 \mathrm{TA}_{3} with Action Include

Here we study the transitions of TA3 when its current action is Include, given different actions of TA4 and input samples. For ease of expressions, the self-loops of the transitions are not depicted in the transition diagram.
Clearly, this situation has 8 instances, depending on the variations of the training samples and the status of $\mathrm{TA}_{4}$, where the first four correspond to the instances with $\mathrm{TA}_{4}=\text{E}$ while the last four represent the instances with $\mathrm{TA}_{4}=\text{I}$.

Now we study the first instance, with $x_{1}=1$, $x_{2}=1$, $y=1$, and $\mathrm{TA}_{4}=\text{E}$. Clearly, this training sample will trigger Type I feedback because $y=1$. Together with the current status of the other TAs, the clause is determined to be $C=\neg x_{1}\wedge x_{2}=0$ and the literal is $x_{2}=1$. From Table [I](#S2.T1), we know that the penalty probability is $\frac{1}{s}$ and the inaction probability is $\frac{s-1}{s}$. To indicate the transitions, we have plotted the diagram showing the penalty probability. Note that the overall probability is $u_{1}\frac{1}{s}$, where $u_{1}$ is defined in Eq. ([4](#S2.E4)). To illustrate the transitions of the TA, we assume here we find a certain $T$ such that $u_{1}>0$ holds.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=1$,

$C=\neg x_{1}\wedge x_{2}=0$.

We here continue with analyzing another example shown below. In this instance, it covers the training samples: $x_{1}=1$, $x_{2}=0$, $y=0$, and $\mathrm{TA}_{4}=\text{E}$. Clearly, the training sample will trigger Type II feedback because $y=0$. Then the clause becomes $C_{3}=\neg x_{1}\wedge x_{2}=0$. Because we now study $\mathrm{TA}_{3}$, the corresponding literal is $x_{2}=0$. Based on the information above, we can check from Table [II](#S2.T2) that the probability of “Inaction” is 1. For this reason, the transition diagram does not have any arrow, indicating that there is “No transition” for $\mathrm{TA}_{3}$.

Condition:
$x_{1}=1$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type II, $x_{2}=0$,

$C=\neg x_{1}\wedge x_{2}=$0.

No transition

The same analytical principle applies for all the other instances, and we therefore will not explain them in detail in the remainder of the paper.

Condition:
$x_{1}=0$, $x_{2}=1$, $y=0$, $\mathrm{TA}_{4}=$E.

Thus, Type II, $x_{2}=1$,

$C=\neg x_{1}\wedge x_{2}=1$.

No transition

Condition:
$x_{1}=0$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=$E.

Thus, Type II, $x_{2}=0$,

$C=\neg x_{1}\wedge x_{2}=0$.

No transition

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type I, $x_{2}=1$,

$C=\neg x_{1}\wedge x_{2}\wedge\neg x_{2}=0$.

Condition:
$x_{1}=1$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type II, $x_{2}=0$,

$C=\neg x_{1}\wedge x_{2}\wedge\neg x_{2}=0$.

No transition

Condition:
$x_{1}=0$, $x_{2}=1$, $y=0$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type II, $x_{2}=1$,

$C=\neg x_{1}\wedge x_{2}\wedge\neg x_{2}=0$.

No transition

Condition:
$x_{1}=0$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type II, $x_{2}=0$,

$C=\neg x_{1}\wedge x_{2}\wedge\neg x_{2}=0$.

No transition

#### 3.1.2 Study TA 3 subscript TA 3 \mathrm{TA}_{3} with Action Exclude

Here we study the transitions of TA3 when its current action is Exclude, given different actions of TA4 and input samples. This situation has 8 instances, depending on the variations of the training samples and the status of $\mathrm{TA}_{4}$. In this subsection and the following subsections, we will not plot the transition diagrams for “No transition”.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=1$,

$C=\neg x_{1}=0$.

Condition:
$x_{1}=0$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type II, $x_{2}=0$,

$C=\neg x_{1}=1$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type I, $x_{2}=1$,

$C=\neg x_{1}\wedge\neg x_{2}=0$.

Condition:
$x_{1}=0$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type II, $x_{2}=0$,

$C=\neg x_{1}\wedge\neg x_{2}=1$.

#### 3.1.3 Study TA 4 subscript TA 4 \mathrm{TA}_{4} with Action Include

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=\neg x_{1}\wedge\neg x_{2}=0$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type I, $\neg x_{2}=0$,

$C=\neg x_{1}\wedge x_{2}\wedge\neg x_{2}=0$.

#### 3.1.4 Study TA 4 subscript TA 4 \mathrm{TA}_{4} with Action Exclude

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=\neg x_{1}=0$.

Condition:
$x_{1}=0$, $x_{2}=1$, $y=0$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type II, $\neg x_{2}=0$,

$C=\neg x_{1}=1$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type I, $\neg x_{2}=0$,

$C=\neg x_{1}\wedge x_{2}=0$.

Condition:
$x_{1}=0$, $x_{2}=1$, $y=0$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type II, $\neg x_{2}=0$,

$C=\neg x_{1}\wedge x_{2}=1$.

### 3.2 Case 2: Include x 1 subscript 𝑥 1 x_{1}

For Case 2, we assume that the actions of the TAs for the first bit are frozen as $\mathrm{TA}_{1}=\text{I}$ and $\mathrm{TA}_{2}=\text{E}$, and thus the overall joint action for the first bit is “$x_{1}$”. Similar to Case 1, we also have 4 situations, detailed in subsections [3.2.1](#S3.SS2.SSS1)-[3.2.4](#S3.SS2.SSS4).

#### 3.2.1 Study TA 3 subscript TA 3 \mathrm{TA}_{3} with Action Include

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=1$,

$C=x_{1}\wedge x_{2}$=1.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type I, $x_{2}=1$,

$C=x_{1}\wedge x_{2}\wedge\neg x_{2}=0$.

#### 3.2.2 Study TA 3 subscript TA 3 \mathrm{TA}_{3} with Action Exclude

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=1$,

$C=x_{1}$=1.

Condition:
$x_{1}=1$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type II, $x_{2}=0$,

$C=x_{1}=1$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type I, $x_{2}=1$,

$C=x_{1}\wedge\neg x_{2}=0$.

Condition:
$x_{1}=1$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type II, $x_{2}=0$,

$C=x_{1}\wedge\neg x_{2}=1$.

#### 3.2.3 Study TA 4 subscript TA 4 \mathrm{TA}_{4} with Action Include

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=x_{1}\wedge\neg x_{2}=0$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type I, $\neg x_{2}=0$,

$C=x_{1}\wedge x_{2}\wedge\neg x_{2}=0$.

#### 3.2.4 Study TA 4 subscript TA 4 \mathrm{TA}_{4} with Action Exclude

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=x_{1}=1$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type I, $\neg x_{2}=0$,

$C=x_{1}\wedge x_{2}=1$.

### 3.3 Case 3: Exclude Both ¬ x 1 subscript 𝑥 1 \neg x_{1} and x 1 subscript 𝑥 1 x_{1}

For Case 3, we assume that the actions of TAs for the first bit are frozen as $\mathrm{TA}_{1}=\text{E}$ and $\mathrm{TA}_{2}=\text{E}$, with 4 situations, detailed in subsections [3.3.1](#S3.SS3.SSS1)-[3.3.4](#S3.SS3.SSS4). Note that in the training process, when all literals are excluded, $C$ is assigned to 1.

#### 3.3.1 Study TA 3 subscript TA 3 \mathrm{TA}_{3} with Action Include

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=1$,

$C=x_{2}=1$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type I, $x_{2}=1$,

$C=0$.

#### 3.3.2 Study TA 3 subscript TA 3 \mathrm{TA}_{3} with Action Exclude

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=1$,

$C=1$.

Condition:
$x_{1}=1$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type II, $x_{2}=0$,

$C=1$.

Condition:
$x_{1}=0$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type II, $x_{2}=0$,

$C=1$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type I, $x_{2}=1$,

$C=0$.

Condition:
$x_{1}=1$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type II, $x_{2}=0$,

$C=1$.

Condition:
$x_{1}=0$, $x_{2}=0$, $y=0$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type II, $x_{2}=0$,

$C=1$.

#### 3.3.3 Study TA 4 subscript TA 4 \mathrm{TA}_{4} with Action Include

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=\neg x_{2}=0$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type I, $\neg x_{2}=0$,

$C=\neg x_{2}\wedge x_{2}=0$.

#### 3.3.4 Study TA 4 subscript TA 4 \mathrm{TA}_{4} with Action Exclude

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=1$.

Condition:
$x_{1}=0$, $x_{2}=1$, $y=0$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type II, $\neg x_{2}=0$,

$C=1$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type I, $\neg x_{2}=0$,

$C=1$.

Condition:
$x_{1}=0$, $x_{2}=1$, $y=0$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type II, $\neg x_{2}=0$,

$C=1$.

### 3.4 Case 4: Include Both ¬ x 1 subscript 𝑥 1 \neg x_{1} and x 1 subscript 𝑥 1 x_{1}

For Case 4, we assume that the actions of TAs for the first bit are frozen as $\mathrm{TA}_{1}=\text{I}$ and $\mathrm{TA}_{2}=\text{I}$, and thus $C=$ 0 always. Similarly, we also have 4 situations, detailed in subsections [3.4.1](#S3.SS4.SSS1)-[3.4.4](#S3.SS4.SSS4).

#### 3.4.1 Study TA 3 subscript TA 3 \mathrm{TA}_{3} with Action Include

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=1$,

$C=0$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type I, $x_{2}=1$,

$C=0$.

#### 3.4.2 Study TA 3 subscript TA 3 \mathrm{TA}_{3} with Action Exclude

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=1$,

$C=0$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{4}=\text{I}$.

Thus, Type I, $x_{2}=1$,

$C=0$.

#### 3.4.3 Study TA 4 subscript TA 4 \mathrm{TA}_{4} with Action Include

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=0$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type I, $\neg x_{2}=0$,

$C=0$.

#### 3.4.4 Study TA 4 subscript TA 4 \mathrm{TA}_{4} with Action Exclude

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=0$.

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{I}$.

Thus, Type I, $\neg x_{2}=0$,

$C=0$.

So far, we have gone through, exhaustively, the transitions of $\mathrm{TA}_{3}$ and $\mathrm{TA}_{4}$ for all possible training samples and system states. In what follows, we will summarize the direction of transitions and study the convergence properties of the system for the given training samples.

### 3.5 Summarize of the Directions of Transitions in Different Cases

Based on the analysis above, we summarize here what happens to $\mathrm{TA}_{3}$ and $\mathrm{TA}_{4}$, given different status (Cases) of $\mathrm{TA}_{1}$ and $\mathrm{TA}_{2}$. More specifically, we will summarize here the directions of the transitions for the TAs. For example, “$\mathrm{TA}_{3}\Rightarrow$ E” means that $\mathrm{TA}_{3}$ will move towards the action “Exclude”, while “$\mathrm{TA}_{4}\Rightarrow$ E or I” means $\mathrm{TA}_{4}$ transits towards either “Exclude” or “Include”.

Scenario 1: Study $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{I}$.

Case 1, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 2, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 3, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 4, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

From the facts presented above, we can confirm that regardless the state of $\mathrm{TA}_{1}$ and $\mathrm{TA}_{2}$,
if $\mathrm{TA}_{3}$ = I and $\mathrm{TA}_{4}$ = I,
they ($\mathrm{TA}_{3}$ and $\mathrm{TA}_{4}$) will eventually move out of their states.

Scenario 2: Study $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{E}$.

Case 1, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E or I.

Case 2, we have:

$\mathrm{TA}_{3}\Rightarrow$ I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 3, we have:

$\mathrm{TA}_{3}\Rightarrow$ I.

$\mathrm{TA}_{4}\Rightarrow$ E or I.

Case 4, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

For Scenario 2 Case 2, we can observe that if $\mathrm{TA}_{3}=\text{I}$, $\mathrm{TA}_{4}=\text{E}$, $\mathrm{TA}_{1}=\text{I}$, and $\mathrm{TA}_{2}=\text{E}$, $\mathrm{TA}_{3}$ will move deeper to “include” and $\mathrm{TA}_{4}$ will go deeper to “exclude”. It is not difficult to derive also that $\mathrm{TA}_{1}$ will move deeper to “include” and $\mathrm{TA}_{2}$ will transfer deeper to “exclude” in this circumstance. This tells us that the TAs in states $\mathrm{TA}_{3}=\text{I}$, $\mathrm{TA}_{4}=\text{E}$, $\mathrm{TA}_{1}=\text{I}$, and $\mathrm{TA}_{2}=\text{E}$, reinforce each other to move deeper to their corresponding directions and they therefore construct an absorbing state of the system. If it is the only absorbing state, we can conclude that the TM converge to the intended “AND” operation.

In Scenario 2, we can observe for Cases 1, 3, and 4, the actions for $\mathrm{TA}_{3}$ and $\mathrm{TA}_{4}$ are not absorbing because the TAs will not be reinforced to move monotonically deeper to the states of the corresponding actions for difference cases.

For Scenario 2, Case 3, $\mathrm{TA}_{4}$ has two possible directions to transit, I or E, depending on the input of the training sample. For action exclude, it will be reinforced when training sample $x_{1}=1$ and $x_{2}=1$ is given, based on Type I feedback. However, $\mathrm{TA}_{4}$ will transit towards “include” side when training sample $x_{1}=0$ and $x_{2}=1$ is given, due to Type II feedback. Therefore, the direction of the transition for $\mathrm{TA}_{4}$ is I or E, depending on the training samples. In the following paragraphs, when “or” appears in the transition direction, the same concept applies.

Scenario 3: Study $\mathrm{TA}_{3}=\text{E}$ and $\mathrm{TA}_{4}=\text{I}$.

Case 1, we have:

$\mathrm{TA}_{3}\Rightarrow$ E or I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 2, we can see that:

$\mathrm{TA}_{3}\Rightarrow$ E or I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 3, we have:

$\mathrm{TA}_{3}\Rightarrow$ E or I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 4, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

In Scenario 3, we can see that the actions for $\mathrm{TA}_{3}=\text{E}$ and $\mathrm{TA}_{4}=\text{I}$ are not absorbing because the TAs will not be reinforced to move deeper to the states of the corresponding actions.

Scenario 4: Study $\mathrm{TA}_{3}=\text{E}$ and $\mathrm{TA}_{4}=\text{E}$.

Case 1, we have:

$\mathrm{TA}_{3}\Rightarrow$ I or E.

$\mathrm{TA}_{4}\Rightarrow$ I or E.

Case 2, we have:

$\mathrm{TA}_{3}\Rightarrow$ I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 3, we have:

$\mathrm{TA}_{3}\Rightarrow$ I.

$\mathrm{TA}_{4}\Rightarrow$ I or E.

Case 4, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

In Scenario 4, we see that, the actions for $\mathrm{TA}_{3}=\text{E}$ and $\mathrm{TA}_{4}=\text{E}$ seem to be an absorbing state, because the states of TAs will move deeper in Case 4. After a revisit of the condition for Case 4, i.e., include both $\neg x_{1}$ and $x_{1}$, we understand that this condition is not absorbing. In fact, when $\mathrm{TA}_{1}$ and $\mathrm{TA}_{2}$ both have “Include” as their actions, they monotonically move towards “Exclude”. Therefore, from the overall system’s perspective, the system state $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{I}$, $\mathrm{TA}_{3}=\text{E}$, and $\mathrm{TA}_{4}=\text{E}$ is not absorbing. For the other cases in the this scenario, there is no absorbing state.

Based on the above analysis, we understand that there is only one absorbing condition in the system, namely, $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{E}$, $\mathrm{TA}_{3}=\text{I}$, and $\mathrm{TA}_{4}=\text{E}$, for the given training samples with AND logic. The same conclusion applies when we freeze the transition of the two TAs for the second bit of the input and study behavior of the first bit of input. Therefore, we can conclude that the TM with only one clause can learn to be the intended AND operator, almost surely, in infinite time horizon.

## 4 Convergence of Analysis of the OR Operator

Once the convergence of the AND operator is proven, it is self-evident that the convergence of the operator OR is also proven. Clearly, if there is one additional NOT gate that is added after the AND operator, the OR operator is achieved. However, this approach requires a change in the structure of the vanilla TM. In fact, the TM can almost surely converge to the intended OR operator if more clauses are given, and the proof is given presently.

To analyse the OR operator, we assume the training samples with the probability below are given.

$$ $\displaystyle P\left(y=1|x_{1}=1,x_{2}=1\right)=1,$ (7) $\displaystyle P\left(y=1|x_{1}=0,x_{2}=1\right)=1,$ $\displaystyle P\left(y=1|x_{1}=1,x_{2}=0\right)=1,$ $\displaystyle P\left(y=0|x_{1}=0,x_{2}=0\right)=1.$ $$

Clearly, there are three sub-patterns of $x_{1}$ and $x_{2}$ that will give $y=1$, i.e., ($x_{1}=1,~{}x_{2}=1$), ($x_{1}=1,~{}x_{2}=0$), and ($x_{1}=0,~{}x_{2}=1$). More specifically, Eq. ([7](#S4.E7)) can be split into three cases, corresponding to the three sub-patterns:

$$ $\displaystyle P\left(y=1|x_{1}=1,x_{2}=1\right)=1,$ (8) $\displaystyle P\left(y=0|x_{1}=0,x_{2}=0\right)=1,$ $$

$$ $\displaystyle P\left(y=1|x_{1}=0,x_{2}=1\right)=1,$ (9) $\displaystyle P\left(y=0|x_{1}=0,x_{2}=0\right)=1,$ $$

and

$$ $\displaystyle P\left(y=1|x_{1}=1,x_{2}=0\right)=1,$ (10) $\displaystyle P\left(y=0|x_{1}=0,x_{2}=0\right)=1.$ $$

In what follows, we will first show that the clauses are able to learn each individual sub-pattern shown in Eqs. ([8](#S4.E8))-([10](#S4.E10)) and then we will show the system behavior when more sub-patterns jointly appear in the training samples without $T$. Thereafter, we conclude the convergence of the system when $T$ is enabled in the learning.

### 4.1 Ability to Learn All the Sub-patterns of OR Operator

The convergence analyses of the above three sub-patterns can be derived by reusing the analyses of the sub-patterns of the XOR operator plus the AND operator. For Eq. ([8](#S4.E8)), we can see that the TAs will converge to $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{E}$, $\mathrm{TA}_{3}=\text{I}$, and $\mathrm{TA}_{4}=\text{E}$, by studying the transition diagrams in Subsections [3.1](#S3.SS1)-[3.4](#S3.SS4) when input samples of $x_{1}=0$, $x_{2}=1$ and $x_{1}=1$, $x_{2}=0$ are removed. In more details, the directions of the transitions for different scenarios are summarized below. The 4 cases mentioned below, i.e., Case 1–Case 4, are defined in Subsections [3.1](#S3.SS1)-[3.4](#S3.SS4).

Scenario 1: Study $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{I}$.

Case 1, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 2, we can see that:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 3, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 4, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Scenario 2: Study $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{E}$.

Case 1, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 2, we have:

$\mathrm{TA}_{3}\Rightarrow$ I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 3, we have:

$\mathrm{TA}_{3}\Rightarrow$ I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 4, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Scenario 3: Study $\mathrm{TA}_{3}=\text{E}$ and $\mathrm{TA}_{4}=\text{I}$.

Case 1, we have:

$\mathrm{TA}_{3}\Rightarrow$ E or I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 2, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 3, we have:

$\mathrm{TA}_{3}\Rightarrow$ E or I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 4, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Scenario 4: Study $\mathrm{TA}_{3}=\text{E}$ and $\mathrm{TA}_{4}=\text{E}$.

Case 1, we have:

$\mathrm{TA}_{3}\Rightarrow$ I or E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 2, we have:

$\mathrm{TA}_{3}\Rightarrow$ I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 3, we have:

$\mathrm{TA}_{3}\Rightarrow$ I.

$\mathrm{TA}_{4}\Rightarrow$ E.

Case 4, we have:

$\mathrm{TA}_{3}\Rightarrow$ E.

$\mathrm{TA}_{4}\Rightarrow$ E.

Comparing the analysis with the one in Subsection [3.5](#S3.SS5), there is apparently another possible absorbing case, which can be observed in Scenario 2, Case 3, where $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{E}$, given $\mathrm{TA}_{1}=\text{E}$ and $\mathrm{TA}_{2}=\text{E}$. However, given $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{E}$, the TAs for the first bit, i.e., $\mathrm{TA}_{1}=\text{E}$ and $\mathrm{TA}_{2}=\text{E}$, will not move only towards Exclude. Therefore, they do not reinforce each other to move to deeper states for their current actions. For this reason, $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{E}$, $\mathrm{TA}_{1}=\text{E}$ and $\mathrm{TA}_{2}=\text{E}$, is not an absorbing state. In addition, given $\mathrm{TA}_{3}=\text{I}$, $\mathrm{TA}_{4}=\text{E}$, $\mathrm{TA}_{1}$ and $\mathrm{TA}_{2}$ with actions E and E will transit towards I and E, encouraging the overall system to move towards I, E, I, and E. Consequently, the system state with $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{E}$, $\mathrm{TA}_{3}=\text{I}$, and $\mathrm{TA}_{4}=\text{E}$ is still the only absorbing case for the given training samples following Eq. ([8](#S4.E8)).

For Eq. ([9](#S4.E9)), similar to the proof of in Lemma 1 in [], we can derive that the TAs will converge in $\mathrm{TA}_{1}=\text{E}$, $\mathrm{TA}_{2}=\text{I}$, $\mathrm{TA}_{3}=\text{I}$, and $\mathrm{TA}_{4}=\text{E}$. The transition diagrams for the samples of Eq. ([9](#S4.E9)) are in fact a subset of the ones presented in Subsection 3.2.1 and Appendix 2 of [], when the input samples of $x_{1}=1$ and $x_{2}=1$ are removed. We summarize below only the directions of transitions.

The directions of the transitions of the TAs for the second input bit, i.e., $x_{2}$/$\neg x_{2}$, when the TAs for the first input bit are frozen, are summarized as follows (based on the subset of the transition diagrams in Subsection 3.2.1 of []).

Scenario 1: Study $\mathrm{TA}_{3}$ = I and $\mathrm{TA}_{4}$ = I.

Case 1: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 2: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 3: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 4: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Scenario 2: Study $\mathrm{TA}_{3}$ = I and $\mathrm{TA}_{4}=\text{E}$.

Case 1: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ I

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 2: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 3: we can see that
$\mathrm{TA}_{3}$ $\rightarrow$ I
$\mathrm{TA}_{4}$ $\rightarrow$ E
Case 4: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Scenario 3: Study $\mathrm{TA}_{3}$ = E and $\mathrm{TA}_{4}$ = I.

Case 1: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ I, or E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 2: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 3: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ I, or E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 4: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

Scenario 4: Study $\mathrm{TA}_{3}$ = E and $\mathrm{TA}_{4}$ = E.

Case 1: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ I

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 2: we can see that
$\mathrm{TA}_{3}$ $\rightarrow$ E
$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 3: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$I

$\mathrm{TA}_{4}$ $\rightarrow$ E

Case 4: we can see that

$\mathrm{TA}_{3}$ $\rightarrow$ E

$\mathrm{TA}_{4}$ $\rightarrow$ E

The directions of the transitions of the TAs for the first input bit, i.e., $x_{1}$/$\neg x_{1}$, when the TAs for the second input bit are frozen, are summarized as follows (based on the subset of the transition diagrams in Appendix 2 of []).

Scenario 1: Study $\mathrm{TA}_{1}$ = I and $\mathrm{TA}_{2}$ = I.

Case 1: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Case 2: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Case 3: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Case 4: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Scenario 2: Study $\mathrm{TA}_{1}$ = I and $\mathrm{TA}_{2}$ = E.

Case 1: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Case 2: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Case 3: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Case 4: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Scenario 3: Study $\mathrm{TA}_{1}$ = E and $\mathrm{TA}_{2}$ = I.

Case 1: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ I, or E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Case 2: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ I

Case 3: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ I

$\mathrm{TA}_{2}$ $\rightarrow$ I

Case 4: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Scenario 4: Study $\mathrm{TA}_{1}$ = E and $\mathrm{TA}_{2}$ = E.

Case 1: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ I, or E

$\mathrm{TA}_{2}$ $\rightarrow$ E

Case 2: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ I

Case 3: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E
$\mathrm{TA}_{2}$ $\rightarrow$ E
Case 4: we can see that

$\mathrm{TA}_{1}$ $\rightarrow$ E

$\mathrm{TA}_{2}$ $\rightarrow$ E

By analyzing the transitions of TAs for the two input bits with samples following Eq. ([9](#S4.E9)), we can conclude that $\mathrm{TA}_{1}=\text{E}$, $\mathrm{TA}_{2}=\text{I}$, $\mathrm{TA}_{3}=\text{I}$, and $\mathrm{TA}_{4}=\text{E}$ is an absorbing state, as the actions of $\mathrm{TA}_{1}$-$\mathrm{TA}_{4}$ reinforce each other to transit to deeper states for the current actions upon various input samples. There are still a few other cases in different scenarios that also seem to be absorbing. But the conditions for those absorbing-like states are not absorbing, making those states not absorbing from system’s point of view. For example, the status $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{E}$ seems also absorbing in Scenario 2, Case 3, i.e., when $\mathrm{TA}_{1}=\text{E}$ and $\mathrm{TA}_{2}=\text{E}$ hold. However, to make $\mathrm{TA}_{1}=\text{E}$ and $\mathrm{TA}_{2}=\text{E}$ absorbing, the condition is $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{I}$, or $\mathrm{TA}_{3}=\text{E}$ and $\mathrm{TA}_{4}=\text{E}$. Clearly, the status $\mathrm{TA}_{3}=\text{I}$ and $\mathrm{TA}_{4}=\text{I}$ is not absorbing. For $\mathrm{TA}_{3}=\text{E}$ and $\mathrm{TA}_{4}=\text{E}$ to be absorbing, it is required to have $\mathrm{TA}_{1}=\text{I}$ and $\mathrm{TA}_{2}=\text{I}$ to be absorbing, or $\mathrm{TA}_{1}=\text{I}$ and $\mathrm{TA}_{2}=\text{E}$ to be absorbing, which are not true. Therefore, all those absorbing-like states are not absorbing. In fact, when $\mathrm{TA}_{3}=\text{I}$, $\mathrm{TA}_{4}=\text{E}$, $\mathrm{TA}_{1}=\text{E}$, and $\mathrm{TA}_{2}=\text{E}$ hold, the condition $\mathrm{TA}_{3}=\text{I}$, $\mathrm{TA}_{4}=\text{E}$ will reinforce $\mathrm{TA}_{1}$ and $\mathrm{TA}_{2}$ to move towards E, I, which is the absorbing state of the system.

Following the same principle, the TAs will converge to $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{E}$, $\mathrm{TA}_{3}=\text{E}$, and $\mathrm{TA}_{4}=\text{I}$ when training samples from Eq. ([10](#S4.E10)) are given, according to the proof of Lemma 2 in [].

### 4.2 System Property without T 𝑇 T

So far, we show that the clauses is able to converge to the intended operator if the training samples for an individual sub-pattern are given. In what follows, we will show that the system becomes recurrent if any sub-patterns of two training samples are given when $u_{1}>0$ and $u_{2}>0$. Specifically, we show that there is no absorbing state for

$$ $\displaystyle P\left(y=1|x_{1}=1,x_{2}=1\right)=1,$ (11) $\displaystyle P\left(y=1|x_{1}=1,x_{2}=0\right)=1,$ $\displaystyle P\left(y=0|x_{1}=0,x_{2}=0\right)=1,$ $$

$$ $\displaystyle P\left(y=1|x_{1}=1,x_{2}=1\right)=1,$ (12) $\displaystyle P\left(y=1|x_{1}=0,x_{2}=1\right)=1,$ $\displaystyle P\left(y=0|x_{1}=0,x_{2}=0\right)=1,$ $$

and

$$ $\displaystyle P\left(y=1|x_{1}=1,x_{2}=0\right)=1,$ (13) $\displaystyle P\left(y=1|x_{1}=0,x_{2}=1\right)=1,$ $\displaystyle P\left(y=0|x_{1}=0,x_{2}=0\right)=1.$ $$

To show the recurrent property when samples following Eq. ([11](#S4.E11)) is given, we need to show that the absorbing states for Eq. ([8](#S4.E8)) disappears when ($x_{1}=1,x_{2}=0,y=1$) is given in addition, and the same applies for Eq. ([10](#S4.E10)) when ($x_{1}=1,x_{2}=1,y=1$) is given.

We first show that the absorbing state for ($x_{1}=1,x_{2}=1,y=1$) Eq. ([8](#S4.E8)), i.e., $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{E}$, $\mathrm{TA}_{3}=\text{I}$, $\mathrm{TA}_{4}=\text{E}$, disappears when sub-pattern ($x_{1}=1,x_{2}=0,y=1$) is given in addition. Indeed, $\mathrm{TA}_{3}$ will move toward E when ($x_{1}=1,x_{2}=0,y=1$) is given, because

Condition:
$x_{1}=1$, $x_{2}=0$, $y=1$, $\mathrm{TA}_{4}=\text{E}$.

Thus, Type I, $x_{2}=0$,

$C=x_{1}\wedge x_{2}=0$.

Clearly, when ($x_{1}=1,x_{2}=0,y=1$) is given in addition,
$\mathrm{TA}_{3}$ has a non-zero probability to move towards “Exclude”. Therefore, “Include” is not the only direction that $\mathrm{TA}_{3}$
moves to upon the new input. In other words, ($x_{1}=1,x_{2}=0,y=1$) will make the state $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{E}$, $\mathrm{TA}_{3}=\text{I}$, $\mathrm{TA}_{4}=\text{E}$, not
absorbing any longer. For other states, the newly added
training sample will not remove any transition from the
previous case. Therefore, the system will not have any new
absorbing state.

Following the same concept, we show that the absorbing state for ($x_{1}=1,x_{2}=0,y=1$) shown in Eq. ([10](#S4.E10)), i.e., $\mathrm{TA}_{1}=\text{I}$, $\mathrm{TA}_{2}=\text{E}$, $\mathrm{TA}_{3}=\text{E}$, $\mathrm{TA}_{4}=\text{I}$, disappears when sub-pattern ($x_{1}=1,x_{2}=1,y=1$) is given in addition. Indeed, $\mathrm{TA}_{4}$ will also move towards E when ($x_{1}=1,x_{2}=1,y=1$) is given, as:

Condition:
$x_{1}=1$, $x_{2}=1$, $y=1$, $\mathrm{TA}_{3}=\text{E}$.

Thus, Type I, $\neg x_{2}=0$,

$C=x_{1}\wedge\neg x_{2}=0$.

Understandably, because of the newly added sub-patterns, the absorbing states in Eqs. ([8](#S4.E8)) and ([10](#S4.E10)) disappear and no new absorbing states are generated. In other words, the TM trained based on Eq. ([11](#S4.E11)), becomes recurrent.

Following the same concept, we can show that the system becomes recurrent for Eqs. ([7](#S4.E7)), ([12](#S4.E12)).
and ([13](#S4.E13)) as well. For sake of conciseness, we will not provide the details here.
In general, any newly added sub-pattern will involve a probability for the learnt sub-pattern to move outside the learnt state and become recurrent.

### 4.3 The Functionality of T 𝑇 T

To encourage the TM to learn different sub-patterns and become possibly absorbed in the OR operator, parameter $T$ plays an important role. The functionality of $T$ is that it can block the training samples for learnt sub-pattern so that the clauses can be guided to learn un-learnt sub-patterns.

###### Theorem 1 .

The clauses can almost surely learn the OR logic in infinite time, when $T\leq\left\lfloor\frac{m}{2}\right\rfloor$.

Proof:
To prove this theorem, we show that (1) $T\leq\left\lfloor m/2\right\rfloor$ is required so that the sum of the outputs of clauses for each sub-pattern can reach $T$. (2) The system is absorbed only when the sum of the outputs of clauses for all sub-pattern reaches $T$ at the same time, i.e., $f_{\Sigma}(C_{i}(\mathbb{X}))=T$, $\forall\mathbb{X}=[x_{1}=0,x_{2}=1]$ or $[x_{1}=0,x_{2}=1]$ or $[x_{1}=0,x_{2}=1]$. (3) the absorbed point can follow all sub-patterns in OR logic. And (4) the input sample ($x_{1}=0,x_{2}=0$) will not have any possibility to give the sum greater than or equal to $T$.

To prove (1), let us look at how to configure $T$ so that the sum of the outputs of clauses for each sub-pattern can reach $T$. The nature of the OR operator offers the possibility to represent 2 sub-patterns jointly. For example, $T$ clauses in the form of $x_{1}$ will result in the sum of the outputs as $T$ for both $(x_{1}=1,x_{2}=0)$ and $(x_{1}=1,x_{2}=1)$. If there are other $T$ clauses to represent the remaining sub-pattern, 2$T$ clauses can offer the sum of outputs as $T$ for any sub-pattern. Clearly, given $m$ clauses in total, when $T=\left\lfloor m/2\right\rfloor$, all sub-patterns can possibly be covered. When we have a smaller $T$, different sub-patterns may be represented by distinct clauses, offering more flexibility. However, when $T>\left\lfloor m/2\right\rfloor$, there will always be one or two sub-patterns that cannot obtain a sum of $T$ clauses. For this reason, the maximum $T$ value is $T=\left\lfloor m/2\right\rfloor$.

To prove (2), we show that the system is not absorbed when 0, 1 or 2 sub-patterns are blocked by $T$, and only when 3 sub-patterns are blocked by $T$, the system becomes absorbed. Clearly, when no sub-pattern is blocked, the training samples given to the system follow Eq. ([7](#S4.E7)). Following this type of training samples, it has already been shown in the previous subsection that the current system status is not absorbing.

Now let’s look at the case when only 1 sub-pattern is blocked. Clearly, if any $T$ clauses block only one sub-pattern, the system is updated based on Eqs. ([11](#S4.E11)), ([12](#S4.E12)), or ([13](#S4.E13)). As stated in the previous subsection, the current system status is not absorbing.

We look at the cases when two sub-patterns are blocked but the third is not blocked. In other words, the sum of the outputs of clauses for any two sub-patterns reaches at least $T$, and the sum for the remaining sub-pattern is less than $T$. In this case, only one type of the samples from Eqs. ([8](#S4.E8)) or ([9](#S4.E9)) or ([10](#S4.E10)) will be given to the TM. Based on the previous analysis of the equations, we understand that all clauses, including the ones that follow the two blocked sub-patterns, will be reinforced to learn the unblocked sub-pattern. This is due to the fact that only the samples following the unblocked sub-pattern are given to the system, and in this circumstance, the system has only one absorbing state, which follows the given training sample.
This property will encourage the clauses that have learnt the blocked sub-patterns move out of the current states. Once they are out of their current states before the sum of the third one also reaches $T$, the blocked sub-patterns will be unblocked and the system becomes one of three cases described by Eqs. ([11](#S4.E11)), ([12](#S4.E12)) or ([13](#S4.E13)). Clearly, the system status is still not absorbing.

In fact, the system will only be absorbed when all three sub-patterns are blocked at the same time. In this situation, no Type I feedback is given and only Type II feedback can possibly update the system. Type II feedback is only triggered by ($x_{1}=0$, $x_{2}=0$, $y=0$) in OR operator. For Type II feedback, based on Table [II](#S2.T2), any transition is only triggered as a penalty when excluded literal has 0 value and the clause is evaluated as 1. Specifically for OR operation, this only happens when $C=\neg x_{1}\wedge\neg x_{2}$ or $C=\neg x_{1}$ or $C=\neg x_{2}$. For $C=\neg x_{1}\wedge\neg x_{2}$, based on the Type II feedback, the TA with the action “excluding $x_{1}$” and the TA with the action “excluding $x_{2}$” will be penalized. In other words, the actions of the TAs for $x_{1}$ and $x_{2}$ will be encouraged to move from exclude to include side. As soon as any one of TAs for $x_{1}$ or $x_{2}$ (or occasionally both of them) becomes included, the clause will become $C=\neg x_{1}\wedge x_{1}\wedge\neg x_{2}$ or $C=\neg x_{1}\wedge\neg x_{2}\wedge x_{2}$ (or occasionally $C=\neg x_{1}\wedge x_{1}\wedge x_{2}\wedge\neg x_{2}$). In this case, input ($x_{1}=0$, $x_{2}=0$) will always result in 0 as the output of the clause and then the Type II feedback will not update the system any longer. Following the same concept, for $C=\neg x_{2}$, the Type II feedback will encourage the excluded $x_{1}$ to be included so that the clause becomes $C=x_{1}\wedge\neg x_{2}$. The same applies to $C=\neg x_{1}$, which will eventually become $C=\neg x_{1}\wedge x_{2}$ upon Type II feedback. When all clauses in $C=\neg x_{2}$ or $C=\neg x_{1}$ are also updated to $C=x_{1}\wedge\neg x_{2}$ or $C=\neg x_{1}\wedge x_{2}$, the system is absorbed because no feedback is triggered up on any input sample.

We summarize the requirement for an absorbing state.

- •
For any sample $\mathbb{X}$ that satisfies OR, i.e. $\mathbb{X}=[x_{1}=1,x_{2}=1]$, or $\mathbb{X}=[x_{1}=1,x_{2}=0]$, or $\mathbb{X}=[x_{1}=0,x_{2}=1]$, the sum of the outputs of clauses, i.e., $f_{\Sigma}(C^{i}(\mathbb{X}))$ must be at least $T$. This will block any Type I feedback.
- •
There are no clauses with only negated literal, such as $C=\neg x_{1}$ or $C=\neg x_{2}$ or or $C=\neg x_{1}\wedge\neg x_{2}$. This will block any Type II feedback.

(3) Now we prove that all the absorbed points can cover all three sub-patterns in OR logic.

Here we employ proof by contradiction. Suppose there is an absorbing state that does not include all sub-patterns in the OR logic. Let’s name the not-included sub-pattern(^2^22There might be more than 1 not-included sub-patterns, but the analysis concept is the same.) as sub-pattern A. For this reason, for any input samples belong to sub-pattern A, the clauses in the absorbing state will not output 1. Therefore, the sum of the clauses for sub-pattern A will not reach $T$, which is a conflict with the requirement for the absorbing state, where the TM needs a sum of at least $T$ clauses for any sub-pattern.

(4) We now show that input sample $(x_{1}=0,x_{2}=0)$ will not give a sum of clause outputs greater than or equal to $T$. This is to avoid any possible false positive case upon input $(x_{1}=0,x_{2}=0)$ in the testing phase. Obviously, to have a positive output, the clause should be in the form of $C=\neg x_{1}$ or $C=\neg x_{2}$ or $C=\neg x_{1}\wedge\neg x_{2}$. It has already shown in (2) that Type II feedback will eliminate such clauses. For this reason, $(x_{1}=0,x_{2}=0)$ will never result in a sum of clause outputs greater than or equal to $T$.

Before the system is absorbed, the system moves back and forth in the intermediate states. As long as $T\leq\left\lfloor m/2\right\rfloor$ holds, the system will eventually be absorbed. We thus have the OR logic almost surely and conclude the proof. $\blacksquare$

Now let us take a look at one example where $m=7$, $T=3$. Due to the randomness of the learning nature, the system may be absorbed in one of numerous absorbing states. Here we list 3 representative ones.

- •
$C_{1}=C_{2}=C_{3}=x_{1}$, $C_{4}=C_{5}=C_{6}=x_{2}$, $C_{7}=*$.
- •
$C_{1}=C_{2}=C_{3}=x_{1}$, $C_{4}=C_{5}=C_{6}=\neg x_{1}\wedge x_{2}$, $C_{7}=*$.
- •
$C_{1}=C_{2}=x_{1}$, $C_{3}=x_{1}\wedge\neg x_{2}$ $C_{3}=C_{4}=\neg x_{1}\wedge x_{2}$, $C_{6}=x_{2}$, $C_{7}=*$.

Here $*$ means the clause can be in any form other than $\neg x_{1}$, $\neg x_{2}$, or $\neg x_{1}\wedge\neg x_{2}$. Note that all above examples can sum up to at least $T$ for any input $\mathbb{X}$ in OR logic.

###### Remark 1 .

When $T$ is greater than half of the number of the clauses, i.e., $T>\left\lfloor m/2\right\rfloor$, the system will not have an absorbing state. We conjuncture that the system can still learn the sub-patterns in a balanced manner, as long as $T$ is not configured too close to the total number of clauses $m$, $s$ is large, and the number of states in the TAs is also large.

Given $T>\left\lfloor m/2\right\rfloor$ the system will oscillate. Nevertheless, with high probability, the system will have at least $m-T$ clauses that follow each sub-pattern, especially when $s$ is large. First of all, when $s$ is large, the clause is less likely to get out of the learnt sub-pattern due to a training sample from the conflicting sub-pattern. This is because of the nature of TM. In more detail, the probability for an included literal in a clause that has learnt a certain sub-pattern to change towards the other sub-pattern is $u_{1}/s$, which only happens when a training sample of the other sub-pattern is given. On the contrary, the reward is $u_{1}\frac{s-1}{s}$ if a training sample of the same sub-pattern is received. $\frac{s-1}{s}>\frac{1}{s}$ holds if $s$ is large. Similarly, when the number of TA states is large, the probability of being in the include side of the TAs is also large given $\frac{s-1}{s}>\frac{1}{s}$.

###### Theorem 1 .

###### Remark 1 .

### 4.4 Revisit the XOR Operator

Let us revisit the proof of XOR operator. As stated in [], when the system is absorbed, the clauses follow the format $C=x_{1}\wedge\neg x_{2}$ or $C=\neg x_{1}\wedge x_{2}$ precisely. In other words, a clause with just one literal, such as $C=x_{1}$, cannot absorb the system. The main reason is that the sub-patterns in XOR operator are mutual exclusive, i.e., the sub-patterns cannot be merged in any way. Although Type I feedback can be blocked when $T$ clauses follow one sub-pattern using one literal, the Type II feedback can reinforce the other missing literal to be included.
For example, when $T$ clauses happens to converge to $C=x_{1}$, the Type I feedback from any input samples of $(x_{1}=1,x_{2}=0,y=1)$ will be blocked. In this situation, the unblocked Type II feedback from $(x_{1}=1,x_{2}=1,y=0)$ will encourage the clause to include $\neg x_{2}$. This is because upon a sample $(x_{1}=1,x_{2}=1,y=0)$, we have Type II feedback, $C=x_{1}=1$, and the studied literal is $\neg x_{2}=0$. When the TA for excluding $\neg x_{2}$ is considered, a big penalty is given to the TA, making it moving towards action Included, and thus $C=x_{1}$ eventually becomes $C=x_{1}\wedge\neg x_{2}$. Following the same concept, we can analyze the development for $C=\neg x_{1}$, $C=x_{2}$, and $C=\neg x_{2}$, which will eventually converge to $C=\neg x_{1}\wedge x_{2}$ or $C=x_{1}\wedge\neg x_{2}$, upon Type II feedback.

## 5 Conclusions

In this article, we prove the convergence of the TM for the AND and the OR operators. Together with the proofs in [] and [], we complete the convergence analyses of TM for the fundamental digital operators, which lay the foundation for future applications and analytical studies of TM.

## Acknowledgements

This work is supported in part by the project Spacetime Vision: Towards Unsupervised Learning in the 4D World financed by the EEA and Norway Grants 2014-2021 under the grant number EEA-RO-NO-2018-04. This work was also
supported by the Research Council of Norway through
the AI4Citizen project (320783) and the AIEverywhere
project (312434).

## Peer Reviews

confidence: 2
contribution: 4
initial_rating: 8
presentation: 3
questions: A question I wonder about is this. It seems to me that the analysis for the OR statement is much harder than that for the AND statement.
Since the convergence for the XOR statement is already established earlier, and for the AND statement in Section 3 of the current paper, could this be used to derive the convergence for the OR statement using a OR b iff (a XOR b) XOR (a AND b), in a much quicker fashion? Perhaps there are technicalities that prevent such an inference, but it would be interesting to know which they are, and if they could be circumvented.
The currect Section 4 gives us more insight into the hyperparameter T, so I do not suggest to replace this section. I am merely interested in whether such inferences are possible.
soundness: 4
strengths: This paper has a very clear project, which I believe is important, and relevant to the ICLR community. The paper answers their two questions, namely: "do TMs converge on the AND and OR operator?" positively, by giving proofs of these claims. The proofs seem correct, but I was unable to check all the details.
I appreciated the choice of the author(s) to include "proof ideas" in Sections 3 and 4.
The writing and presentation is mostly very good. I have some slight suggestions for improvement, which I will list in the section "Weaknesses".
summary: This paper studies Tsetlin Machines (TMs). It builds on earlier papers, and in particular on an earlier paper that shows that clauses will converge almost certainly to the XOR logic operator. In this paper, the author(s) intend to answer the same question for the AND and OR operators.
The author(s) notes that upon completing this project, the convergence of all basic operators in Boolean algebra will be established. This certainly makes the questions relevant, and the paper does indeed address these questions.
The author(s) gives proofs for their claims, both in detail in the appendix, as well as the idea in the main text (wherever appropriate). Because of this, and because as far as I can tell the proofs seem correct, their claims are well supported.
The new knowledge that this paper reports is certainly interesting for anyone who studies or uses TMs. Therefore, this paper is relevant for the ICLR community.
weaknesses: I think this is a good paper, so my weaknesses are less important than the strengths I identified in the section 'Strengths".

The main weakness, in my opinion, is that the paper does not convey the idea behind a TM well. What are the main ideas behind a TM? What are they used for? Being a non-expert, I had to look this up.
I understand and appreciate that it might not be possible to accommodate for this in general due to page limitations, but I do recommend that the author(s) streamlines some of the presentation, in particular:
- On line 052, the author(s) talks about the hyperparameter T. A bit later, on line 105 they talk about a threshold Th, which later turns out to be related to T. Later on, they mostly talk about T again, and relate this twice to Th. It is still not clear to me how to think about Th and T exactly. For instance in Eqs (2) and (3) it would be useful to know what T is. I recommend to make this more clear.
- On Lines 139 – 147 the authors talk about the two types of feedback they generate. It would be helpful to know an (informal) argument about why these feedbacks precisely are used.

I end this section with a list or minor remarks and typos:
- Line 172: It would be useful to indicate the start and end of the proof idea. As I said earlier, I do like the choice of including the proof idea in the main text.
- Line 226: "we can concluded that" shoud be "we can conclude that".
- Line 228: "we must frozen TA3" shoud be "we must freeze TA3" or something along those lines. 
- Line 290: "samples following Eq. (8) is given' should be "samples following Eq. (8) are given'.
- Line 291: "the absorbing states for Eq. (t) disappears" should be "the absorbing states for Eq. (t) disappear".
- Line 452: I believe that "We conjuncture" should read "We conjecture".

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: - **Q1:** What are the challenges of generalizing this result and the previous ones for XOR, AND, and OR to the >2-bit cases? 
- **Q2:** What are the challenges when having numerical data as inputs? How do you suggest handling non-binary datasets in TMs? Specifically, what techniques could binarize data while minimizing potential biases?
- **Q3:** Have you considered generalizing beyond propositional logic? I am fond of logic, and it would be nice to know if the authors have in their research agenda to extend their results to more expressive logics, such as modal and/or first-order logic. This aspect is also essential as a considerable amount of real-world data comes from signals hardly modeled using static Boolean vectors/masks.
- **Q4:** I don't understand why the authors claimed in Theorem 2 that "[...] the OR logic [...]" when their result applies to 2-bit inputs only. Indeed, Equation 4 (right before Theorem 2) presents four 2-bit inputs. Am I missing something here? Consider clarifying in Theorem 2 that the result applies specifically to 2-bit OR logic, or explain how it generalizes to n-bit cases if that's the case.
- **Q5 (minor):** Are there any reasons why you have used a poorly formatted citation style throughout the paper? I would have expected to see, e.g., (Granmo, 2018) instead of Granmo (2018).
soundness: 4
strengths: - **S1:** Clear mathematical formulation.
- **S2:** Precise collocation in the relevant literature, and therefore, the paper addresses a novel problem
- **S3:** Great illustrations to help the reader.
summary: The paper's main contribution addresses the missing piece for TM's convergence: AND and OR operators. Previous studies have analyzed (and published after peer review) the 1-bit NOT and IDENTITY operators and the 2-bit XOR case. This paper fills the remaining gap (as far as I understand) in 2-bit AND and OR operators. The final result of this paper is to complete the bigger picture of logical operators interpreted over the Boolean algebra. The paper is already in a solid position to be accepted, but minor changes could improve the overall comprehensibility.
weaknesses: - **W1:** As far as I understand, the results are limited to 2-bit cases. This limitation is essential as real-world data rarely have only 2-bit input.
- **W2:** I may be wrong, but perhaps the interdependence between clauses is the reason previous proofs and those presented in this paper have not generalized to >2-bit cases. 
- **W3:** To learn TMs, non-binary datasets must necessarily be transformed into binary ones. As far as I understand the literature, further research is needed to address this issue. Applying naive techniques to binarize datasets could potentially introduce biases during the transformation.
- **W4:** After a quick search on the Internet, I found an arXiv version of this paper with the same name and typos (see https://arxiv.org/abs/2109.09488). For example, search for ".)." (i.e., extra ".") in both PDFs and there will be a perfect match for the same typos (in the four cases). As such, the authors are likely the same. I am not sure if that was the original intention, but nevertheless, this strategy does not entirely fulfill the double-blind process.

---

confidence: 2
contribution: 1
initial_rating: 8
presentation: 2
questions: Can you clarify the questions regarding the theoretical background I raised in the bullet points in the weaknesses section? Should these questions have been resolved from any part of your paper (if yes, where?), or do you assume these as a background a reader should have?

In Eq (1), what is the semantic difference between the testing and training formula? The usual convention is for the empty conjunction to be defined as true, if you differ from that this should be mentioned.

Can you give an example for a machine learning task where TM would be applicable? What would be the TM input and output in that example and how would the TA within the TM look like?

How do the theoretical results you show in this paper affect the use of TM in practice?

minor comments:

* the citation style without parentheses is strenuous to read, please use \citep (see point 4 in ICLR style guidelines)
* line 56: "...while this paper searches for absorbing states" -- what does "this paper" refer to in this sentence? From the grammar I would assume your own submission, but form context rather the paper by Zhang et al. (2022) or Jiao et al. (2022)
* line 64 "learnt" -> learned
soundness: 2
strengths: The problem discussed in the paper is a natural continuation of previous works and, based on this line of research, seems to be of interest for the community. The relevance for the paper is hinted at by citing several use cases for TM.

The structure of the paper is straight forward, with each of the two main sections being dedicated to one of the two operators for which convergence is discussed.

I like the loop-back to the previous work on the XOR-operator, establishing a more detailed comparison to other recent results.
summary: The paper aims to show the convergence of Tsetlin machines (TM), a relatively new machine learning approach based on Tsetlin automata (TA), for AND and OR operators. After previous work has done work on the convergence for the XOR operator, as well als the IDENTITY and NOT operators, this fills the gap to show convergence for standard binary operators.
weaknesses: From this paper, it is very hard to grasp the concept of how TM are used for machine learning applications for anyone not familiar with TM. The usefulness of the main theoretical results of the paper -- the convergence of TM for the AND and OR operator -- also very much remains unclear since it is not discussed.

Also on a technical level this paper does not convey how TM and TA work in the first place. Despite reading through section 2 and appendix A, I did not gain an understanding of what a TM is. To exemplify this, even the start of the first sentence in the preliminaries ("A TM that is to learn the sub-patters of class $i$ is formed by $m$ teams of TAs in the form of clauses, $C^i_j(X), j=1,2,...,m$, where $X$ is the input of a TM, and $X=[x_1,x_2,...,x_o],x_k\in ${$0,1$}$, k=1,2,...,o$.") raises several questions that are never addressed in the paper:

* What is a class here?
* What do you mean by sub-patterns of a class?
* How is a TA even defined?
* From what I read from related work, a TA is a probabilistic automaton. How is it represented by a clause?
* What is a team of TAs? Is it different to just a set of TAs (and if yes, in which way)?
* What are the $x_k$ in the input to a TM?

Many of the definitions, e.g. the definition of $\xi^i_j$ (line 90) or the concept of polarity (line 102ff), are not given in a formal way but only in plain language, making the theoretical foundation of the paper very imprecise.

Most importantly, "convergence" is neither defined nor explained for TM. This makes one of the main statements of the paper, Theorem 1, impossible to understand from the paper alone.

For future revisions I **highly** suggest to make the paper self-contained and make sure that anyone not familiar with TM (which I imagine will be a large fraction of audiences) is able to follow the ideas of the paper. I also want to mention that large parts of the preliminaries including figures, are copied from related work, such as Jiao et al. (2022), Zhang et al. (2022) and Granmo (2018). While they are properly cited and this only affects preliminaries (and thus I do not see concerns regarding plagiarism), I think it would be highly beneficial for this paper to set up its definitions, tailored to the setting of this paper, in order to enhance understandability.

Based on the lack of formal definitions I was not able to follow sections 3 and 4 and cannot give detailed feedback on it.

At the end of section 4, experiments validating the theoretical results are mentioned. However, discussion on the experiments are fully shifted into the appendix. In my opinion, they should also be discussed in the main part of the paper.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 1
questions: In light of the above comments: 
* Can the convergence proofs for AND and OR be extended to noisy/agnostic settings? 
* Alternatively, do these convergence proofs still hold in the presence of many irrelevant variables?
soundness: 2
strengths: The authors demonstrate that TMs can almost surely learn the AND and OR relations with the simplest structures, under noise-free conditions.
summary: This paper examines Tsetlin Machines (TMs), a machine learning architecture characterized by notable attributes such as transparent inference and a hardware-friendly design. While recent literature has established convergence properties for the identity, negation, and exclusive-or operators, this study completes the analysis by establishing the convergence of the “AND” and “OR” operators.
weaknesses: **Audience:**
The paper primarily focuses on Tsetlin Machines, particularly their capability to learn logical concepts such as AND and OR in a noise-free environment. However, it does not address other potential approaches that can also learn these simple concepts under similar conditions. Consequently, the paper seems tailored to a niche group of researchers invested in Tsetlin Machines, raising doubts about its relevance to the broader ICLR community.

**Significance:**
The introduction highlights that the main motivation for studying Tsetlin Machines is their interpretability, as their inference is explainable and their learning process is transparent. A crucial question arises: "Are there other interpretable models and transparent algorithms capable of learning logical concepts under noise-free conditions?" The clear answer is yes. Noise-free concept learning is merely equivalent  to "proper and realizable PAC learning," which has been thoroughly explored since the 1980s. Notably, when the target function is a conjunction, disjunction, or exclusive disjunction of literals over two features, the class of 2-DNF formulas covers all these target concepts. Additionally, 2-DNF is both properly and efficiently PAC learnable in the realizable setting, with a sample complexity that is logarithmic in the input dimension - see e.g. landmark papers such as Valiant (1984) and Haussler (1988), and Shalev-Shwartz and Ben-David’s book (2014). Finally, set cover algorithms for learning disjunctions, and more generally k-DNF, are entirely transparent (see e.g. Marchand and Shawe-Taylor, JMRL 2002).

Even if we focus solely on the results concerning Tsetlin Machines, it seems that Jiao et al. (2022) have already established a foundation for learning binary relations, particularly the XOR operation. As a result, the current study, which investigates the convergence of other binary relations (AND, OR), appears to have limited significance, despite some technical differences. Additionally, since the learning process assumes ideal, noise-free conditions without irrelevant variables, this contribution is relatively minor.

**Clarity:**
The paper presents significant readability challenges due to issues with formatting and punctuation. Specifically, citations should be enclosed in brackets, and punctuation should be used sparingly. For instance, the sentence “In TM, after training, a certain clause, in propositional logic, is a conjunction of literals [...]” (Line 32) notably impacts the paper's clarity.

Additionally, for the ICLR community, it is crucial to provide a clear background on these architectures. Unfortunately, Section 2 falls short in this respect. Key concepts such as Tsetlin Automata (TA) and the notion of a team are mentioned without adequate explanation. Actually, I had to consult the papers by Abeyrathna et al. (2021) and Jiao et al. (2022) to fully understand these concepts.

Meta-review: The paper proves that Tsetlin Machines can learn OR and AND operators.  This is a theoretical paper that advances the understanding of the capabilities of Tsetlin Machines.  The strengths of this paper are the theoretical contributions.  The weaknesses include the presentation that assumes expertise with Tsetlin Machines and a lack of discussion and theoretical comparison to other work in learning theory that shows that other models can also learn the OR and AND operators.

Decision: Reject