You are using intuition about real computers and trying to apply it to Turing Machines. Real computers have limits that Turing Machines do not.
When it comes to Turing machines, the increase in the size of the data set is not an issue. A Turing machine has an infinitely long tape, so adding a finite amount of extra data to it is no problem. All you need to do is show that for any given Turing Machine, there exists a "reified" version which encodes the rules of the original machine as data on the tape. This was proven by Alan Turing.
When it comes to real machines, which have finite limits, the story is much more complicated. For starters, no real computer is actually Turing Complete. They are actually finite automata, limited by things like memory. The "Turing Completeness" of real computers really argues that the abstract instruction set is theoretically unbounded (for example, you could hook it up to a tape drive of arbitrary length).
When you look at this different domain, the story fits more with your intuition. Computers tend to be unable to run faster than themselves. However, there is a devil in the details of how you define this. Optimization creates really complicated corner cases. For example, if I consider the loop in C++:
int m = 0;
int n = 0;
for(int i = 0 ; i < 1000000000; i++) {
for (int j = 0; j < 1000000000; j++) {
for (k = 0; k < 1000000000000; k++) {
n = n + 1;
}
}
}
std::cout << "M is " << m << std::endl;
It would take a very long time for the computer to "run" this. It has to do a giant nested loop which takes a long time. However, if we reify this, permitting the computer to effectively look at the source code (or machine code, or whatever), its easy to see that that big loop does not affect the value of m. We can skip the loop entirely.
The ability to do this is at the root of all compilers. And, indeed, it gets done at runtime as well. Consider the java code
int sum = 0;
for (int i = 0; i < myArray.length; i++) {
sum += myArray[i];
}
By the rules of the language, we are obliged to check that myArray[i] does not access a value past the end of myArray. We are supposed to check it every time. However, this is slow. So most java runtime environments are smart enoguh to recognize the bytecode emitted by the sort of pattern and only do the array length check once. Thus we have a case where simply executing the byte code as written is slower than reifying it into instructions, analyzing them mathematically, and emitting a new "faster" program.
Of course, its trivial to show that there must be at least one program which is as-fast-as-possible.
While I wont get into the details of it, microprocessors do this as well. No processor currently produced actually runs x86 or x64 instructions. x86 is an abominably slow instruction set. Instead, they all analyze the x86 instructions and emit "microcode" which is much faster to execute. For example, the microcode can show opportunities to pipeline which aren't always valid for a string of instructions, but can be shown to be valid for this one.
