halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever
Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist
to prove this, he described a paradox involving a concept now known as "Turing machine"