3 ms·
Why is it wrong? If the oracle can only identify a certain class of nonterminating programs, you still get a speed up by doing so.
by tree_of_item 8y ago
Why is it wrong? If the oracle can only identify a certain class of nonterminating programs, you still get a speed up by doing so.
- empath75 8y agoIf you told me you wanted to count through all the natural numbers but we’re going to skip the evens, how much time would you save.
- yters 8y agoIn the article's scenario there are a finite number of Turing machines to check in order to find one that matches the specification. So, eliminating some of them will lead to a speed up.