4 ms·
Could you explain "above arithmetic in the hierarchy" in a few words, TIA, never heard of this
by _a_a_a_ 3y ago
Could you explain "above arithmetic in the hierarchy" in a few words, TIA, never heard of this
- eesmith 3y agoNope. The source page links to https://en.wikipedia.org/wiki/Arithmetical_hierarchy https://en.wikipedia.org/wiki/Arithmetical_hierarchy . I can't figure it out. An HN comment search, https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=Arithmetical%20hierarchy&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu... , finds a few more lay examples, with https://news.ycombinator.com/item?id=21210043 https://news.ycombinator.com/item?id=21210043 by dwohnitmok being the easiest for me to somewhat make sense of. I think the idea is, suppose you have an oracle which tells you if a Turning machine will halt, in finite time. There will still halting problems for that oracle system, which requires an oracle from a higher level system. (That is how I interpret "an oracle that magically gives you the answer to the halting problem for a lower number of interleavings will have its own halting problem it cannot decide in higher numbers of interleavings").
- BoiledCabbage 3y agoThis appears to discuss it a bit more. Not certain if it's more helpful than the comment (still going through it), but it does cover it more in detail. https://risingentropy.com/the-arithmetic-hierarchy-and-computability/ https://risingentropy.com/the-arithmetic-hierarchy-and-compu...