I think a better way to describe the halting problem would be: There isn't a program or algorithm of lower complexity which can prove that a specific program actually terminates.