When running A, in some cases you would necessarily need more memory to run it than the memory bound that you defined for the input program, if you want it to work for all input programs without mistakes and without saying "don't know".
But that doesn't say anything about the time complexity, or does it?
The same argument applies to time complexity as well. A' is A plus some trivial logic, so its running time should be marginally higher. A' halts with input A' iff A says A' does not halt within the desired time bound with input A'. That's a contradiction if A is substantially faster than the time bound.
You are making an interesting argument but I am having a bit of difficulty in understanding it.
So instead of saying: does program X with input X halt?
You redefined the problem to be: does program X with input X halt within T time steps?
Then you reach the conclusion: A' halts with input A' iff A says A' does not halt within the desired time bound with input A'.
But OK, imagine that we define the time bound T to be 10 steps and so A can always tell you whether a program halts within 10 steps, and always gives the correct answer in 1 step. What does that tell us?
> Then we can write a program A' that runs A with the input. If A says that the input halts (within the bound), A' enters an infinite loop.
So:
1. If A says (in 1 step) that X halts in the first 10 time steps, then A' enters an infinite loop.
2. If A says (in 1 step) that X doesn't halt in the first 10 time steps, then A' halts (say, in the second step).
Now you run A' with A' as input and:
1. If A says (in 1 step) that A' halts in the first 10 time steps, then A' enters an infinite loop.
2. If A says (in 1 step) that A' doesn't halt in the first 10 time steps, then A' halts (say, in the second step).
But here's the thing: A can only efficiently, correctly and always prove whether X halts if A is able to use more memory than X would use (otherwise we'd run into the exact same undecidability problem as with Turing machines).
This implies that besides the time bound, A also needs to analyze whether X halts within a defined memory bound.
So when you run A' with A', for A to work correctly then A would have to use more memory than A' would use, which is a contradiction because A' needs to use as much or more memory than A.
So isn't it impossible to use A' with A' as an input if you want A to always give you a correct answer, regardless of the time complexity bound? Because the memory bound would always be exceeded.
Does that actually prove that it's impossible to construct such a time-efficient A that works for all X that use less memory, or does it only prove that it's impossible to run A with A' as input correctly because the memory bound would always be exceeded?
Exactly.
When running A, in some cases you would necessarily need more memory to run it than the memory bound that you defined for the input program, if you want it to work for all input programs without mistakes and without saying "don't know".
But that doesn't say anything about the time complexity, or does it?