Before Rust, I used to believe that certain applications were fundamentally difficult to write without a GC.
With Rust, with all problems I have seen so far, with a bit of design, most to seem Rc/Weak quite well.
Question: Are there any well known problems (ex: halting problem, diamond hierachy, dining philosopher) taht fundamentally requires a GC?
No.
There are some things involving atomic pointers that more or less require a garbage-collection step of some sort if you want to avoid a lock. For an example, check out epochs and hazard pointers.
An interesting problem concurrent collections deal with comes from the remove operation. Suppose that a thread removes an element from a lock-free map, while another thread is reading that same element at the same time. The first thread must wait until the second thread stops reading the element. Only then it is safe to destruct it.
Programming languages that come with garbage collectors solve this problem trivially. The garbage collector will destruct the removed element when no thread can hold a reference to it anymore.
(from the epoch link above)
If you're implementing an interpreter for a garbage collected language, you'll fundamentally need to use or implement a garbage collector.
More generally, if you're truly dealing with 1. a graph of objects 2. that has a changing structure you cannot predict in advance 3. and may contain loops 4. but which nonetheless requires disconnected loop to be cleaned up, then you're going to need some runtime garbage collector.
And, in fact, there are crates which address that niche, like gc_derive. However, it's a pretty rare niche.