# Tag Info

230

Because a lot of really practical problems are the halting problem in disguise. A solution to them solves the halting problem. You want a compiler that finds the fastest possible machine code for a given program? Actually the halting problem. You have JavaScript, with some variables at a high security levels, and some at a low security level. You want to ...

53

In practical terms, it is important because it allows you to tell your ignorant bosses "what you're asking is mathematically impossible". The halting problem and various NP-complete problems (e.g. the traveling salesman problem) come up a lot in the form of "Why can't you just make a program that does X?", and you need to be able to give an explanation of ...

47

You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1). To do that, you need to store at least two copies of the partial state of the program in memory, plus the overhead of the checking program. So on a given computer, you cannot test all programs that can execute on that computer,...

45

A pretty simple example could be a program testing the Collatz conjecture: $$f(n) = \begin{cases} \text{HALT}, &\text{if n is 1} \\ f(n/2), & \text{if n is even} \\ f(3n+1), & \text{if n is odd} \end{cases}$$ It's known to halt for $n$ up to at least $5 × 2^{60} ≈ 5.764 × 10^{18}$, but in general it's an open problem.

38

Here is a proof of undecidability by reduction from the Halting problem. Reduction: Given a machine $M$ and an input $x$, build a new Turing Machine $H$ which does not read any input, but writes $M$ and $x$ on the tape and simulates $M$ on $x$ until $M$ halts. The behaviour of this new machine $H$ is independent of the input tape, so it is a pure Turing ...

33

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. "We" are not an algorithm =) There is no general algorithm that could determine if a given program halts for every program. What are the simplest (smallest) ...

31

It seems to me that the Halting Problem is nothing more than a so called "paradox," a self referencing (at the very least cyclical) contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions No, that's not what the halting problem is about. Paradoxes like the liar'...

27

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. Hence, Turing's proof will not 'fail' in the spacetimes, it will simply not prove anything about the relation of the halting problem and time dilation. However,...

25

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine with finite memory will either halt or repeat a previous state. You can use the algorithm which detects whether a linked list loops to implement the Halting ...

23

There are indeed programs like this. To prove this, let's suppose to the contrary that for every machine that doesn't halt, there is a proof it doesn't halt. These proofs are strings of finite length, so we can enumerate all proofs of length less than $s$ for some integer $s$. We can then use this to solve the halting problem as follows: Given a Turing ...

22

Computational complexity studies the computational resources required to decide problems in some particular model of computation. Because of this, it makes no sense to talk about the complexity of a problem that is not computable in the model of computation you're talking about. Or, to put it the other way around, it only makes sense to talk about the ...

21

Short version: The outputs of the machines are not correct or incorrect, they are just contradictory, which proves that the initial machine that decides whether the input machine halts on the given string or not can't exist. Long version: First we'll sketch the proof (or at least one version of it - there are many). Assume that we have a Turing Machine $\... 21 is halting problem computable by program P for all other programs used as input but P itself? No. Consider the infinite sequence of programs$P_1, P_2, \dots$, where$P_i$is "Move the head$i$squares to the right, then$i$squares to the left, then do exactly what$P$would do." Every one of these programs produces exactly the same output as&... 20 It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context. Remember that Turing knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (... 20 You're exactly right that the halting problem is an example of the second kind of "proof by contradiction" - it's really just a negative statement. Suppose decides_halt(M) is a predicate that says that machine M decides if its input is a machine that halts (that is, M is a program that for some machine m and input i, decides if m halts on input i). ... 20 I don't think this is a good way to present the halting problem, because it sweeps a critical issue under the covers in a sneaky way. I suggest sticking with a more standard presentation, such as the one you linked. If you want to find a way to explain it in a way that minimizes the technical content, the presentation in this video is surprisingly ... 20 Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of its variants for instance. It's common for the soundness of a type system to boil down to proving that all programs normalize in it. Strong normalization is a ... 19 The halting problem is solvable for any Turing machine which uses a known bounded amount of space, by a generalization of the argument given by Yonatan N. If the amount of space is$S$, the alphabet size is$A$, and the number of states is$Q$, then the number of possible configurations is$QSA^S$. If the machine halts then it must halt within$QSA^S$steps, ... 19 jmite has answered the question really nicely. Let me add a small side-note regarding the perceived similarity with the "Liar's Paradox" which I think is caused by their usage of a self-reference mechanism. Self-reference is not paradoxical! Self-reference is a really useful tool in computation (that an algorithm can refer to its code, reflection) and ... 19 In your edit, you write: What I still don't see is what would motivate someone to define$D(M)$based on$M$'s "self-application"$M;M$, and then again apply$D$to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you ... 19 A TM s just a program. It does whatever you program it to do. If, for instance, you program it to perform the following: while (true) { do_nothing } , then it will never halt! The language$L$goes over all possible machines$M$, and therefore it must encounter some machines that don't halt, for instance, the one stated above. There is a deep ... 19 The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO. In other words,$\emptyset$is decidable. You might be confused with the fact that the language of Turing machines whose language is empty is undecidable. That is, there is no Turing machine that, on input$T$, decides ... 18 The Church-Turing thesis says that the informal notion of an algorithm as a sequence of instructions coincides with Turing machines. Equivalently, it says that any reasonable model of computation has the same power as Turing machines. An artificial intelligence is a computer program, i.e., an algorithm. If the Church-Turing thesis holds, then you could ... 18 As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number in R. From that we can create an (infinite but) countable list of numbers in R. Now we can apply Cantor's diagonal argument directly to prove that there still ... 17 Just take a problem whose Turing degree is above$0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above$\Sigma^0_1$. Examples of such problems (where$\phi_n$is the$n$-th partial computable function and$W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$is the$n$-th ... 17 The halting problem is not a statement about intelligence (human or artificial) it is a statement about the limits of mathematics. It is an historically important example of an undecidable problem. An artificial (or human) intelligence can certainly look for and find many sorts of different infinite loops in real programs. And the halting problem doesn't ... 17 Well, you can always consider a Turing machine equipped with an oracle for the ordinary Turing machine halting problem. That is, your new machine has a special tape, onto which it can write the description of an ordinary Turing machine and its input and ask if that machine halts on that input. In a single step, you get an answer, and you can use that to ... 17 Don't worry – everybody gets confused by the direction of reductions. Even people who've been working in algorithms and complexity for decades occasionally have a, "Wait, were we supposed to be reducing$A$to$B$or$B$to$A$?" moment. Reducing$A$to$B$produces a statement of the form "If I could solve$B\$, then I'd also ...

17

It's actually much simpler. There's only a countable number of algorithms. Yet there are uncountably many real numbers. So if you try to pair them up, some real numbers will be left hanging.

16

You seem to be confusing the classic "self referential" based proof that the Halting problem cannot be solved with the Halting problem (aka Halt) itself. That self-referential program -- the program that halts if and only if it doesn't halt -- is constructed in order to make it easy to prove you cannot solve Halt. The fact that we prove X is impossible via ...

Only top voted, non community-wiki answers of a minimum length are eligible