# Tag Info

Accepted

### Why, really, is the Halting Problem so important?

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 ...

### Why, really, is the Halting Problem so important?

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. ...

### Why, really, is the Halting Problem so important?

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 ...
Accepted

### What are the simplest examples of programs that we do not know whether they terminate?

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{...
Accepted

### Is the halting problem decidable for pure programs on an ideal computer?

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$ ...

### Why, really, is the Halting Problem so important?

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 ...

### What are the simplest examples of programs that we do not know whether they terminate?

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. "...
Accepted

### Is it provably true/false that for a program, there exists a proof whether it halts or not?

Actually this is no different from the halting problem unsolvability. If you have any formal system T with a proof verifier program V that can reason about programs (as you desire in your question), ...
Accepted

### Turing machine + time dilation = solve the halting problem?

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. ...

### Why, really, is the Halting Problem so important?

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 ...

### Are there programs that never halt and have no non-termination proof?

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,...
Accepted

### Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

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 ...
Accepted

### Does the proof of undecidability of the Halting Problem cheat by reversing results?

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 ...
Accepted

### Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

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 ...

### Is halting problem computable for particular inputs/assumptions

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$ ...
Accepted

### Halting Problem without self-reference: why does this argument not suffice (or does it)?

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 ...
Accepted

### Is possible to prove undecidability of the halting problem in Coq?

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 ...
Accepted

### Halting problem theory vs. practice

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 ...
Accepted

### Can a program exist that halts only if it can prove that it doesn't halt?

We can define a sound proof system as a computable function $\Pi$ which maps strings (proofs) to strings (statements proved), with the following property: if $\Pi(\pi) = p$, then $p$ encodes a true ...

### Why, really, is the Halting Problem so important?

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 ...

### Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

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 ...
Accepted

### Why won't a Turing machine halt?

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 ...

### Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

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 ...
Accepted

### The 'directionality' of reductions?

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 ...
Accepted

### Does Church-Turing thesis also apply to artificial intelligence?

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 ...
Accepted

### How to prove the existence of a number which cannot be written by any algorithm?

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 ...

### Are there any existing problems that wouldn't be solvable with a halting oracle?

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 ...

### Why, really, is the Halting Problem so important?

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 ...