In my reading of GEB, Hofstadter was criticizing other authors who disagreed with his understanding of the Church-Turing thesis (that human intelligence is, or at least is not more powerful than, some kind of rule-following system). Hofstadter thinks that there is no inherent contradiction or essential difference in kind between the human who "can step out of a system" and the computer "just blindly executing the commands given to it".

(But Hofstadter didn't explain at a technical level how to make a computer that's as intelligent as a human being.)

As mentioned, humans can step out of a system and analyze it objectively. In essence, the rules can be broken and changed at any time, which means the system is constantly evolving. Logic does not always truly need to play a part, either. The system is constantly changing and adjusting.

Because of this limitation due to our inability to implement systems that are truly nondeterministic, we are forced to use the constantly improving resources (such as faster processors, memory, better algorithms) to improve the speed at which we can mimic this behavior. However, these methods still require the data at hand to function, and several of them lead to exponential growth. As you said, it is always limited to what it's given.

Anyone who does any coaching work is intensely aware of these limits (in everyone, btw, the coach included!)...