Sign up
Please tick the below box to proceed
I agree (or if I am under 13 my parent or guardian agrees on my behalf) to the terms and conditions of use and that:
- My test statistics may be published on the site leaderboard against my username
- My teacher(s) can review my test scores
- I can receive feedback on my tests from my teacher(s)
Please tick this box to proceed
Already have an account? Sign in
Preview lessons, content and tests
Computer Science & Programming solved. All in one platform.
1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.2. Searching for something specific? See our text overview of all tests. Scroll right for levels, and lists. 3. Student and Teacher User Guides | Schemes of Work | Real Teacher use Videos |
Join 36000+ teachers and students using TTIO.
Halting Problem
The halting problem is a decision problem in computability theory. It asks, given a computer program and an input, will the program terminate or will it run forever? For example, consider the following Python program:
x = input()
while x:
pass
For example, in pseudocode, the programIt reads the input, and if it's not empty, the program will loop forever. Thus, if the input is empty, the program will terminate and the answer to this specific question is "yes, this program on the empty input will terminate", and if the input isn't empty, the program will loop forever and the answer is "no, this program on this input will not terminate".
while (true) continue
does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program
print("Hello World")
does halt.
The Halting problem is perhaps the most well-known problem that has been proven to be undecidable; that is, there is no program that can solve the halting problem for general enough computer programs. Source: https://brilliant.org/wiki/halting-problem