Decision problem: http://en.wikipedia.org/wiki/Decision_problem
These are fairly foundational concepts when talking about computational complexity.
Ok so upon reflection I think I see what you are getting at. Practical computers are have limited memory and so are, in principle, equivalent to a finite state machine.
So anything a practical computer can do a, perhaps ridiculously large, regular expression can also do?
Is that close?