17 ms·
> By your definition, all problems of the form “does program X have property Y” are decidable, because you can just simulate X on all possible inputs until it h
by wizeman 4y ago
> By your definition, all problems of the form “does program X have property Y” are decidable, because you can just simulate X on all possible inputs until it halts or cycles, and observe whether Y holds in each case.
Yes! Thank you! That's exactly what I'm saying.
Now the question is: how can we do this without having to simulate running the program step-by-step on all possible inputs?
Or in other words, how can we reduce the time complexity of the currently-known algorithms for solving this problem?
That's the actual interesting question!
- Nevermark 4y agoOk, but unless you stick with some fixed resource limit N forever, the problem is undecidable again. I suppose we could pick a very large resource number N (allocatable between time and memory space?) and agree that we will create a large body of math and algorithms with the assumption of that limit, so all our theorems and programs within that finite math area are consistent. But a great deal of math would have to be reconsidered every time N was increased.
- wizeman 4y ago> Ok, but unless you stick with some fixed resource limit N forever, the problem is undecidable again. Why do you believe that? The existence of the cycle detection algorithms that I mentioned earlier don't assume any particular number N and yet they prove that the problem is decidable as long as N is assumed to be a finite number.
- Nevermark 4y agoAh! Very good point!! Thank you.