The issue is mostly a historic artifact, not an impossibility of implementation.
The way most C compilers build code is so that the compiler only sees each source file at a time; it never sees the whole program at once. When one source file calls a function from another source file or a library, all the compiler sees is the header file with the return type of the function, not the actual code of the function. This means when there is a function that returns a pointer, the compiler has no way to tell if the memory that the pointer is pointing to needs to be freed or not. The information to decide that is not shown to the compiler at that point in time. A human programmer, on the other side, is free to look up the source code of the function or the documentation to find out what needs to be done with the pointer.
If you look into more modern low-level languages like C++11 or Rust you'll find that they mostly solved the issue by making memory ownership explicit in the type of the pointer. In C++ you would use a
unique_ptr<T> instead of a plain
T* to hold memory and the
unique_ptr<T> makes sure that the memory gets freed when the object reaches the end of the scope, unlike the plain
T*. The programmer can hand the memory from one
unique_ptr<T> to another, but there can only ever be one
unique_ptr<T> pointing at the memory. So it is always clear who owns the memory and when it needs to be freed.
C++, for backward compatibility reasons, still allows old style manual memory management and thus the creation of bugs or ways to circumvent the protection of a
unique_ptr<T>. Rust is even more strict in that it enforces memory ownership rules via compiler errors.
As for undecidability, the halting problem and the like, yes, if you stick to C semantics it is not possible to decide for all programs when the memory should be freed. However for most actual programs, not academic exercises or buggy software, it absolutely would be possible to decide when to free and when not to. That's after all the only reason why human can figure out when to free or not in the first place.