> If theory of computation has taught us anything, is that complexity very quickly outgrows everything that is even in the grasp of mathematics (e.g. busy beave

> If theory of computation has taught us anything, is that complexity very quickly outgrows everything that is even in the grasp of mathematics (e.g. busy beaver). True. But if the science/practice of computation has taught us anything, it is that many problems can be solved for all practical purposes even if they are undecidable or intractable for all theoretical purposes. E.g., the halting problem is undecidable but software verification/static analysis tools that check for termination exist and are even widely used in some industries. > A human in theory can “go into a loop” A computer can as well, by identifying loop invariants. And even the discovery of loop invariants can be thought of as a next-token-prediction problem, if characterized in as a sequence of states followed by the question "if x_1=t_1, ..., x_n=t_n, then what are these variables equal to at state N+1?" > So - I guess GPT-4 can reason on the “trivial” degree simply by “caching” the output of the real algorithm, but that doesn’t scale at all. I am more-or-less in agreement about GPT-4, but I think claims about the limitations of the architecture/problem statement are over-stated.