unless you are allowed to pose infinitely many problems
Or one selected at random from an infinite class of problems.
Also, if the universe is spatially infinite, it can solve the halting problem in a deeply silly way, namely there could be an infinite string of bits somewhere, each a fixed distance from the next, that just hardcodes the solution to the halting problem.
That’s why both computability theory and complexity theory require algorithms to have finite sized sourcecode.
Or one selected at random from an infinite class of problems.
That’s why both computability theory and complexity theory require algorithms to have finite sized sourcecode.