Comment by benkuykendall
Comment by benkuykendall 3 days ago
> Getting to Turing completeness can require polynomial CoT tokens, wrt the input problem size.
So, as stated, this is impossible since it violates the Time Hierarchy Theorem.
The actual result of the paper is that any poly-time computable function can be computed with poly-many tokens. Which is... not a particularly impressive bound? Any non-trivial fixed neural network can, for instance, compute the NAND of two inputs. And any polynomial computable function can be computed with a polynomial number of NAND gates.
> The actual result of the paper is that any poly-time computable function can be computed with poly-many tokens.
You're right.
Re: NAND of two inputs. Isn't this doable even by a single layer (no hidden layers) neural network?
Re: Polynomial computable function. I'm assuming this makes no assumption of constant-depth.
Because my entire point was that the result of this paper is not actually impressive AND covered by a previous paper. Hopefully that's clearer.