3 ms·
> If we only have a partial halting oracle, we still get a speed up by eliminating the non-halting programs that can be identified by our partial oracle. This
by empath75 8y ago
> If we only have a partial halting oracle, we still get a speed up by eliminating the non-halting programs that can be identified by our partial oracle.
This is wrong on so many levels that the entire rest of the essay becomes nonsense.
- tree_of_item 8y agoWhy 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.
- yters 8y agoYou may want to check out the proof for further information. https://news.ycombinator.com/item?id=18377525 https://news.ycombinator.com/item?id=18377525
- yters 8y agoDirect link: https://www.am-nat.org/site/law-of-information-non-growth/ https://www.am-nat.org/site/law-of-information-non-growth/