3 ms·

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' i

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.

deleted 4y ago
[deleted]
wizeman 4y ago
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?

deleted 4y ago

[deleted]

wizeman 4y ago

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?