The halting problem is a fundamental concept in computability theory that refers to the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run indefinitely.

• Computability theory
• Theoretical computer science
• Software engineering
• Artificial intelligence

Consider a simple program that takes a single input string and prints either ‘yes’ or ‘no’ depending on whether the input is a palindrome. If the input is not a palindrome, the program will run indefinitely. Determining whether such a program will halt for a given input is an example of the halting problem.

• Effective Problem Formulation