Currently open questions that would not require infinite memory to evaluate computationally

Question

I was reading an old thread over at the code golf / code challenge Stack Exchange, which asks users to come up with a computer program for which it is an open question whether it terminates.

My first thought was that one would have to assume the computer has infinite memory, because for example, if you want to look for odd perfect numbers then sooner or later you will reach integers whose binary representation is too large for a finite amount of memory.

But I wonder if that's necessarily the case. Perhaps there are open questions that could be determined computationally without infinite memory, because (for example) they involve checking all the permutations of some finite sequence, such that it would take an extremely long time to check computationally, while having a known bound on the amount of space.

So formally, I suppose I'm asking for a Turing machine for which it is known that it will never leave a particular bounded region of its tape (and those bounds are known), but it is not known whether or not it halts. I'm fine with informal answers though.

(I suppose a technically correct answer would be "are there any odd perfect numbers less than $10^{2000}$?", but this is kind of cheating - I'm looking for answers where the bound on memory is a natural part of the conjecture, rather than just set above the current known bound.)

Answer 1

Sounds like you're looking for nontrivial uncomputable functions. For that, I recommend exploring the busy beaver function; it is uncomputable, but it is possible to explore all possible permutations of Turing machines at some of the lower-ended state counts to see which one produces the maximal number of 1's. Hence, we've found the numerical values of $\Sigma(3)$ and $\Sigma(4)$, but not $\Sigma(5)$. Any Turing machine solution to $\Sigma(n)$ must necessarily halt and use a finite amount of memory, but actually determining whether any arbitrary $n$-state Turing machine halts is... well, uncomputable.

So in that sense, it is an open conjecture that $\Sigma(5) = 4098$, and proving or disproving it would not take an infinite amount of memory- just some assumptions regarding the lack-of-termination of some Turing machine configurations.

Answer 2

I nominate the first Skewes' number, defined as the smallest positive integer such that $\pi(x)$ $\gt$ $\operatorname{li}(x)$. The number has been proved to exist, and upper bounds have been successively refined down to $\simeq 10^{316}$ but "there is no explicit value x known for certain to have the property π(x) > li(x)" yet.