-2
$\begingroup$

I had the experience several years ago of working with a team that had developed a ternary computing system. It ran out of funding and was abandoned but I felt it was ahead of its time. Currently, what is the state of this (ternary computing) research and development? Is there a place online that one could suggest to look for more information?

$\endgroup$
10
  • 1
    $\begingroup$ I think that for current models of computation it doesn't matter if the computer is binary, ternary, or $k$-ary for any constant $k$. $\endgroup$ – Laakeri Apr 26 at 19:18
  • 1
    $\begingroup$ It affects the complexity only by a constant factor, and constant factors are very rarely/never analyzed. $\endgroup$ – Laakeri Apr 26 at 19:31
  • 1
    $\begingroup$ The Linear Speedup Theorem (effectively) says that the alphabet size for TMs only matters up to constant factors. This is shown via some symbol carpooling argument. The same basically holds for most other models as well, up to possible caveats about needing to read the whole input. In the concrete example of 2 vs 3 symbol RAM machines, it's clear that a 4-symbol machine can directly simulate a 3-symbol machine, but 2 symbol machine can simulate a 4-symbol machine by considering pairs of symbols at a time. E.g. 00=0, 01=1, 10=2, 11=3. $\endgroup$ – Yonatan N Apr 26 at 19:33
  • 1
    $\begingroup$ There are modular gates, which sum their inputs and compare against 0 mod p. You could consider these as taking in values [0,p-1]. But I'm not sure if that's what you're looking for. $\endgroup$ – Jake Apr 26 at 19:37
  • 1
    $\begingroup$ @Jake is there a paper you can point to that I can review? $\endgroup$ – tale852150 Apr 26 at 19:50
0
$\begingroup$

Modular counting gates are probably the closest thing in complexity theory to what you're asking about. Modular gates sum their inputs and compare against 0 mod $p$. Many authors consider these gates as taking in values in the range $[0,p-1]$ since you can hook multiple wires between pairs of gates. This paper provides a good summary of results in the area up until its publication date (2010) and a result on probabilistically emulating the AND function with just modular gates in constant depth.

As far as it relates to your original question, much more focus is given to composite moduli of two distinct prime factors (e.g. 6) than to prime moduli such as 3, since the computational power of a composite modulus with distinct factors is greater and much less well understood, as the linked paper describes.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.