Would it not be possible to scan an app to determine exactly what libraries it could load? I think you can avoid halting problem issues by simply doing a dumb search for the library load routines in the code, at the possible (but not very likely) problem of picking up spurious data in a binary blob section.
There are tools that do this (for example, proguard). The issue is that java can dynamically load code, so static analysis isn't sufficient. Typically for areas where code size matters (like on Android), you use static analysis plus a manual list.
