First of all, we need to agree on what does a correct disassembly of a binary program is. I would propose the following definition:
A correct disassembly of a binary program will give the set of all the possible instructions that can be executed by the program whatever input it takes.
Another way to state it would be to say that we expose the instructions of all the possible executions of the program on every input it can take.
Here we already can make a parallel with the halting problem on a Turing machine which can be defined as follow (Wikipedia):
The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
This (apparently) very simple problem has been shown undecidable by Turing, meaning that, even if we can handle a certain amount of cases automatically with a program, some pathological cases will always escape from our program which will fail to tell if yes or no the machine/program will halt on the given input.
And, of course, such pathological cases are infinitely many (so, there is no hope to enumerate them one after one as special cases).
Back to our disassembly problem!
Exploring all the possible paths of a program is indeed undecidable because of the halting problem!
Indeed, a dual way to formulate the halting problem is the accessibility problem where you want to know if there is an input that allow you to reach a specific point of the program. And, knowing if a specific place in memory can be reached by the program and interpreted as an instruction (i.e. the instruction pointer takes the value of this address at some point) is an accessibility problem.
So, disassembly is undecidable.
But, In The Real World ?
I know, I know, this is only Math... Not reality... Most of the obfuscations (voluntary or not) can be worked out and automatically removed from binary code...
Well, this was essentially because people who did these obfuscations were not used to undecidable problems...
Imagine that you insert in your program the computation of an undecidable problem, or even, just something hard and complex enough that will break any automated reasoning applied to it.
To give an example, lets take the Collatz sequence (Wikipedia), this sequence is conjectured to always end at 1 after some time. But, the arithmetic problem behind it is so tremendously complex that this conjecture holds since about one century... This is a perfect opaque predicate to use! Of course, it might be that the proof of such conjecture exists, but this problem is complex enough to start building on it and confuse computer exploring the state space of a program.
In fact, this is the current direction of research in strong obfuscation nowadays... We are almost done with the small tricks that were used before and people start to build things on better grounded problem. Even if we still miss an equivalent of a Shannon (father of the information theory) in matter of software obfuscation to be compared with cryptology.
So, we saw that the disassembly problem is strongly linked to the halting problem. And, also, that using highly complex problems might be the next step in modern software obfuscation.
I would just have a final word about the fact that current disassembly tools are probably way behind what we could do if we had to stick with the state of the Art in disassembly techniques. I am always crying in pain when I see how prehistoric are the current tools... but putting all the modern techniques into practice would require so much effort of development and maintenance that nobody seems to be ready to do it (but this is only my humble opinion).