# what is halting problem? [duplicate]

i have researched it on wikipedia and it produces me an unusual example and stories about Turing,so what i understand is if an program run in loop,an electronic device in cpu or in computer structure would stop that program,or an code will be processed by the input to decide if the program will be executed or will be halted after that.So what is the halting problem actually?

Consider the set of all possible pairs $\langle M, w \rangle$, where $M$ is a Turing machine and $w$ is some string on a fixed alphabet. Also note that some $M$ may halt on input $w$, and some may not.

Basically, the Halting problem asks to create a Turing machine that takes a pair $\langle M, w \rangle$ as input, and eventually halts with answer "YES" if $M(w)$ halts, and "NO" if $M(w)$ does not halt.

If you are familiar with programming you could interpret this problem as following. The Halting problem asks you to write a C++ program which reads another target program together with its input written in C/C++, and always stops and prints "YES" if the target program eventually stops on the input, and prints "NO" otherwise. Note that your program must work for any finite size of target program and any finite size of input.

As for its history, this is one of famous David Hilbert's 23 questions posed in 1900 at the Second International Congress of Mathematicians in Paris, and later in 1936 was solved by Alan Turing to show that such algorithm deciding on all possible pairs $\langle M, w \rangle$ cannot exist.

This Wikipedia article provides a formal definition of the problem and sketch of proof.

• i'm not familiar with those symbols but i familiar with c and bash and javascript.But how can an program can run arbitrarily and loop forever?An program(an stream of electric signal bit) will be executed(the processed bits go to cpu and go out RAM and peripheral devices).Now when the program has been sent out,it will have to be repeated by the ROM or RAM and keep take input data.The program can run background and manipulate the other programs but it doesn't mean that that program will run arbitrarily? Dec 4 '17 at 12:37
• @Lan... while (x > 0) { x=4; } loops forever, for instance, if initially $x$ happens to be $>0$.
– chi
Dec 4 '17 at 12:43

You should be familiar with the concept of coding of a program if we want to explain Halting Problem informally without using formal definition of Turing machine.

Coding of a program contains all instructions that the program follows to process its input. Let's call coding of program $P$ as $<p>$.

Suppose someone gives a $<p>$. Can you understand will $P$ outputs anything and halt if it runs input $w$? You can not unless you run $w$ on $<p>$ and wait to see its result.

The point of this experiment is that if $P$ halts you will understand at a time in future, but you'll never understand if stuck in a loop. Note that you don't know how long you should wait to see its result and this makes the halting problem hard.

Halting problem says there is no program $\mathcal{P}$ that given $<p>, w$ as its input and can determine whether $P$ will halt running $w$ or not.

To better intuition, let's define two languages.

$$L_{halt}=\{(<p>,w)| \text{P halts on w}\}\\ L_{\overline{halt}}=\{(<p>,w)| \text{P doesn't halts on w} \}.$$

As I explained above you can enumerate $L_{halt}$ but you can't do it for $L_{\overline{halt}}$. Halting problem says you can't write any program that given $(<p>,w)$ and decides whether $(<p>,w) \in L_{halt}$ or $(<p>,w) \in L_{\overline{halt}}$.

Edit: I changed check membership of $L_{halt}$ to enumerate with the subtle point Yuval mentioned.

• "Can you understand will $P$ outputs anything and halt if it runs input w? You can not unless you run $w$ on $\langle p\rangle$ and wait to see its result." Not necessarily. There could be other ways. Dec 4 '17 at 14:07
• "[Y]ou can check membership of $L_{halt}$ but you can't do it for $L_{\overline{halt}}$." The two problems are equivalent, and none of them is computable. You can enumerate $L_{halt}$. Dec 4 '17 at 14:08
• @YuvalFilmus I can imagine of other ways if, for example, we knew $<p>$ is a C++ code or any other specific programming language. But I think when we have no idea what is the coding about and we just know that is a coding, there is no other way. Would you please name some other ways if you know? Dec 5 '17 at 3:08
• The problem is that it's hard to prove that there is no other way. Dec 5 '17 at 6:24
• "Halting problem says there is no program P that given ANY <p>,w as its input and can determine whether P will halt running w or not". You should mention that the Halting Problem says there is no program "P" that can do that for every other (program,input) pair. Jun 12 '18 at 1:52