I think what you’re describing is very roughly equivalent to Busy Beaver numbers: https://en.m.wikipedia.org/wiki/Busy_beaver

This kind of assumes that “A simple problem, involving basic arithmetic and small numbers, 1, 2, and 3” can be encoded into some bounded-state Turing machine.