FFT is easy fairly easy for transformers to find as a pattern.
Note that OpenAI admits that pre-training (pattern finding and matching) is where the abilities on professional tests comes from.
Even proofs in presburger arithmetic have an upper bound on the second level of the polynomial hierarchy, which is way beyond the computational power of any LLM
https://arxiv.org/abs/2207.00729
>The model’s capabilities on exams appear to stem primarily from the pre-training process and are not
significantly affected by RLHF. On multiple choice questions, both the base GPT-4 model and the
RLHF model perform equally well on average across the exams we tested
https://arxiv.org/abs/2303.08774
To practically scale, parallelism is required, and the ability to find algorithms within the L or TC0 complexity classes is limited.
Remember that individual ANNs as used in transformers are just binary linear classifiers. Which you can do a lot with, but probably limited to P assuming we don't find out L or TC0 are larger than we think now.
Presburger arithmetic, or first order logic with (+,=), or (*,=) is the strongest FoL that is both complete and consistent. move up to Peano arithmetic and you start to hit the limits from Gödel, Church, and Turing.
There will be instances that an LLM can learn with CoT, zero shot etc...
But most of those will be due to luck or parallel patterns in the training set.
LLMs simplicity bias is great for plausible answers to our of distribution questions, but puts limits on what can be learned as far as 'algorithms' go.
They will work for 'there exists' problems far better than for any 'for all' or 'for most' problems unless they have learnable patterns in the training set.