On Computable Numbers, with an Application to the "Entscheidungsproblem" (1936) 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"