I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational primitives could exist, that are sometimes more useful than numbers.

Modern CPUs provide efficient "circuit-parallel" primitives for addition, subtraction, multiplication, division, square-root, and inverse-square-root. I believe those are all contained in TC0. The primitives provided by modern CPUs also include address logic (multiplexer-circuits), which I believe are contained in AC0. The arithmetic primitives are actually also useful for address logic related tasks (and related data structures), at least to a certain extent.

Assuming that those totally different computational primitives conjectured by XYZ really exist, how plausible is it that they are actually contained in TC0 (or NC1), such that it would have been possible for modern CPUs to provide them as "useful primitives"? (Maybe the multiplexer-circuits give some hint that there really could be such primitives, if we allow that the number of input bits can be totally different from the number of output bits.)

  • $\begingroup$ What CPUs could provide is first of all limited by what can be actually realized in hard-ware. As far as I understand it, the circuits we know how to make are made of threshold gates. Or am I wrong? This a priori limits the possible primitives to TC0, as long as the time needed by each instruction ($\approx$ depth of the circuit) is $O(1)$. $\endgroup$ Sep 10 at 5:56
  • $\begingroup$ @EmilJeřábek When I looked into how "circuit-parallel" functionality is done in FPGA and ASIC, I was disappointed how often they simply fall-back to lookup-tables based on multiplexer-circuits. This can violate the polynomial size constraint, but apparently that is acceptable. So in the end it seems to be the other way round, namely the "useful primitives" we wanted to have turned out to be in TC0. More basic building blocks like the multiplexer-circuits are typically even in AC0. The absence of primitives from NC1 doesn't seem to be caused by manufacturability constraints. $\endgroup$ Sep 10 at 8:11

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.