Rice’s Theorem: An interactive tutorial

Re:Rice’s Theorem: An interactive tutorial by jltsiren on Friday November 25, 2022 @11:01PM (#33749780)

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.

[ Parent | on HN ]

Re:Rice’s Theorem: An interactive tutorial by wizeman on Friday November 25, 2022 @11:55PM (#33750135)

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?

[ Parent | on HN ]