The first line of Sipser book for the Chapter- 'Time complexity', says that:
Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the solution requires an inordinate amount of time or memory.
My question is, yes we do have limited space and time, so the above statement makes the whole P and PSPACE concept as vague, right? If it so, what are these problems? Are such huge inputs acceptable in practice?
Given an integer k, are there integers (positive or negative) x, y, z with an absolute value ≤ $10^{1000}$ such that $x^3 + y^3 + z^3 = k$?
It is believed that without the limit on the absolute values the answer is "Yes" unless $k \equiv 4 \mod 9$ or $k \equiv 5 \mod 9$. On the other hand, solutions are so rare that most likely solutions for some values k cannot be found in the lifetime of the universe.
And both the inputs, and the space needed for a computation, are tiny. The limitation on the size of x, y, z makes it decidable.
If you consider space and time limitation, it'll be safe to assume that almost every Decidable problem (as per the exact definition) can have version that can be computationally not solvable.
That said, Turing machines are not a practical model for computing. Even in the theoretical computer science community, the more realistic RAM machines are used in the areas of algorithms and data structures. The concept of P - PSPACE are all dependent on Turing Machine, the method to classify a decidable/undecidable problem and hence must not be correlated with the practicality.
However, for sake of example:
Relevant Stuff:
