News for hackers. Stuff that matters.
Re:Apollo 11 vs. USB-C Chargers (2020) by _a_a_a_ on Wednesday December 27, 2023 @06:07AM (#38780878)
Could you explain "above arithmetic in the hierarchy" in a few words, TIA, never heard of this
Re:Apollo 11 vs. USB-C Chargers (2020) by eesmith on Wednesday December 27, 2023 @10:29AM (#38782891)
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").

Re:Apollo 11 vs. USB-C Chargers (2020) by BoiledCabbage on Wednesday December 27, 2023 @12:44PM (#38784388)
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...