I recommend Gregory Chaitin's book intended for a popular audience. It is short, and a good introduction to algorithmic information theory for non-mathematicians. Chaitin's Constant (Omega) is a non-computable number that is equivalent to the halting problem.
[0]: https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/14...