2
$\begingroup$

It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length?

I have a proof scratch that the automaton in question should be no more complex than a non-deterministic PDA:

Let addition be express by $L = \{1^n0^m1^{n+m}\}$ where $1^n$ represent the first term, $0^m$ represent the second term, and $1^{n+m}$ is the sum of those terms.

Theorem:

$L$ is context free.

Proof:

It is trivial to show that a non-deterministic PDA can store $n$ and $m$ in the stack by pushing a symbol to the stack when a symbol from the first or the second term is read.

Once both terms have been read, the PDA can read the sum and remove item from the stack. The PDA accepts the string if the stack is empty after all symbols of the sum has been read. The PDA otherwise rejects the string.

Since there is a PDA that recognizes $L$, $L$ is context free.

Theorem:

$L$ is not regular.

Proof:

Suppose $L$ is regular, by pumping lemma for regular language, there is a pumping length $p$ such that $\forall w \in L, |w| \geqslant p$, $w = xyz$ such that $|xy| \leqslant p$, $|y| \geqslant 1$, $\forall n \geqslant 0, xy^nz \in L$.

Let $x = 1^n$, $0 \leqslant n < p$, $y = 0^{p - n}$, $z = 1^p$. $xy^0z = 1^n1^p \not \in L$. Contradiction.

Therefore, $L$ is not regular.

$\endgroup$
  • $\begingroup$ Why can't x be 11...1100? And, why can't y be 100...00? You're still picking convenient ways of splitting w. Note, you could handle all the possible cases of x and y, or you could wisely pick w, so you don't have to bother. $\endgroup$ – Karolis Juodelė Nov 5 '18 at 14:17
  • $\begingroup$ @D.W. I reworded it into a question. $\endgroup$ – Mys_721tx Nov 5 '18 at 18:04
  • 1
    $\begingroup$ @Raphael in the example, all strings in $L$ are some form of $n + m = (m + n)$ and a machine computes addition by accepting $L$. I thought in this way, I can get away with not having output. Unary encoding is allowed, and it is not limited to models that only compute addition in unary encoding. $\endgroup$ – Mys_721tx Nov 5 '18 at 22:23
  • 1
    $\begingroup$ @Mys_721tx Right, that's a reasonable decision version. In binary, I don't think PDAs can do it. In unary, a single counter (either variant) suffices, which is weaker than a stack iirc. $\endgroup$ – Raphael Nov 5 '18 at 22:53
  • 1
    $\begingroup$ Addition can be computed by a finite state transducer if the two input numbers are fed in parallel, so the input alphabet consists of pairs of digits. The construction is given in this (negatively valued) question: What is this DFA doing (carry bits)? $\endgroup$ – Hendrik Jan Nov 9 '18 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.