Real programs can solve problems given enough time and space. For every problem instance of known size, there is fixed upper bound on the amount of space which is consumed.
Are there problems that cannot be solved (i.e. functions which cannot be computed), given "just" a sufficiently large memory?
More concretely, are there functions which can only be computed by a Turing Machine (which has infinite tape), but not by a conventional program?
It is not possible for a Turing machine to actually consume an infinite amount of tape during any particular execution, because it must halt after a finite number of steps. If it does not halt, then it has not "solved" anything. Since the machine can only run for a finite number of steps, it can only move a finite distance from its starting point in either direction, and thereby consume only a finite amount of tape.
More concretely, are there functions which can only be computed by a Turing Machine (which has infinite tape), but not by a conventional program?
Sure. But only by virtue of requiring an unreasonable (finite) amount of time or space.
