Hacker News new | ask | show | jobs
by _a_a_a_ 912 days ago
Could you explain "above arithmetic in the hierarchy" in a few words, TIA, never heard of this
1 comments

Nope. The source page links to 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&qu... , finds a few more lay examples, with 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").

This 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-compu...