How can Turing complete machines exist theoretically if the halting problem is undecidable
The halting problem is the problem of deciding whether a given Turing machine halts on a given input or not.

This problem is undecidable, meaning that no program running on a Turing machine can solve this problem for all possible inputs. Hence, your assumption that such a program exists is wrong.