Thread1: takes lock A, ..., tries to take lock B
Thread2: takes lock B, ..., tries to take lock A
Looks like you should be able to pass Mutex<A> and Mutex<B> to both threads otherwise what's the point of mutex if there's no way to share data protected by it, so it doesn't look like it prevents you from hitting this scenario.
In the trivial example you gave, one strategy just insists we take locks in alphabetical order. Thread 2 can't take lock A, because it already has lock B and that's not the correct order.
The common method for deadlock-free code is roughly that when a thread is required to wait on a lock owned by a second thread, it checks to see if the second thread is waiting on a lock already owned by the first thread. This requires that the lock graph essentially be a high-performance and concurrent global structure.
Locks like this can be expensive, particularly under high concurrency or contention, so they aren't used for most software. If you can fit your software in a simpler model e.g. where locks are singular or only acquired as a DAG, then much higher performance options are available that don't require deadlock detection.
I wonder if it is similar to the halting problem. Can deadlocks even be prevented in theory?
The mechanism is costly but elegant. If a lock you are trying to acquire is owned by another thread, you inspect the locks you own to determine if that thread is waiting on one of your locks. When a deadlock is detected, there are several strategies to automatically resolve it e.g. rolling back one of the threads to a point where forward progress can be safely serialized.
No one wants to use these mechanics for ordinary code, due to their cost. For the fashionable thread-per-core software architectures, deadlocks aren't something you commonly have to worry about.