6 ms·

"LLMs, without pattern matching, can only do up to about integer division, and while they can calculate parity, they can't use it in their calculations." - what

• nyrikki 2y ago
  Yes, in this case PARITY is determining if the number of 1s in a binary input is odd or even It is an effect of the complex to unpack descriptive complexity class DLOGTIME-uniform TC0, which has AND, OR and MAJORITY gates. http://arxiv.org/abs/2409.13629 http://arxiv.org/abs/2409.13629 The point being that the ability to use parity gates is different than being able to calculate it, which is where the union of the typically ram machine DLOGTIME with the circuit complexity of uniform TC0 comes into play. PARITY, MAJ, AND, and OR are all symmetric, and are in TCO, but PARITY is not in DLOGTIME-uniform TC0, which is first-order logic with Majority quantifiers. Another path, if you think about symantic properties and Rice's theorem, this may make sense especially as PAC learning even depth 2 nets is equivalent to the approximate SVP. PAC-learning even depth-2 threshold circuits is NP-hard. https://www.cs.utexas.edu/~klivans/crypto-hs.pdf https://www.cs.utexas.edu/~klivans/crypto-hs.pdf For me thinking about how ZFC was structured so we can keep the niceties of the law of the excluded middle, and how statistics pretty much depends on it for the central limit and law of large numbers, IID etc... But that path runs the risk of reliving the Brouwer–Hilbert controversy.