# Questions tagged [halting-problem]

Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.

66 questions
Filter by
Sorted by
Tagged with
7k views

### What is the complement of Halting Problem?

I understand that Halting problem is 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 forever. ...
• 133
174 views

• 133
272 views

### The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages

Can the following two statistics be bounded: the proportion of halting programs vs non-halting programs the proportion of decidable vs undecidable languages For example, can we say that one class is ...
• 1,624
402 views

### Misunderstanding Turing's Halting-Problem Argument

I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM_MtS_w4) . I’m having some difficulty understanding the argument as it is made. Let me explain it ...
• 21
127 views

### State whether the language is in $R$, $RE$, etc. The intuition for the solution

I saw the solution but can't understand the intuition of the following question: Let's define $$L^{\ge k} = \{w\in L : |w| \ge k\}$$ and L=\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^...
847 views

### Halting problem for fixed Turing machine and fixed input

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$. What if we fixed both the machine and the input? I.e., is it decidable for every ...
1 vote
2k views

### The Halting problem proof is wrong?

First, let's see the pseudocode proof of halting problem: P(x) = run H(x, x) if H(x, x) answers "yes" loop forever else halt Then we have a ...
• 175
1 vote
122 views

### Turing machines: can a machine write to a finite number of memory cells, but not halt?

I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it ...
1 vote
2k views

### Is the halting problem decidable by an "infinite Turing machine"?

It has been shown of course that the halting problem is undecidable. That is, we cannot formulate a Turing machine that will decide for any arbitrary turing machine whether it will halt or not. ...
• 3,982
1 vote
594 views

### Does a DPDA halt on all inputs?

Given a deterministic DPA, is it possible to tell whether it halts on all possible inputs? Is this problem decidable? The standard halting problem is "Given a DPDA and an input $x$, determine ...
• 161k
95 views

### Do proofs of $HALT$'s undecidability make it clear that it's practically relevant?

The proof of $HALT$'s undecidability usually goes like this: we assume the existence of a halting decider and incorporate it into a machine $D$ that takes a TM as input, runs it on its own encoding ...
243 views

### Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not

It is known that the halting problem is decidable for every fixed $M_0$ Turing machine and every fixed $w_0$ input. My related question would be the following: is it true that for every fixed $M_0$ ...
37 views

### how is the set of undecidable programs related to the set of non-halting programs?

Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting? Thanks!
• 365
266 views

### Halting problem. Decider “recognising itself” in the input?

This is about the halting problem. My questions are: where do you think are logical flaws in what I am going to write? How do you think this does not invalidate the proof for the undecidability of the ...
• 1
I'm interested in this functions \begin{align*} g(m) &= \begin{cases} \text{defined} & \text{if turing machine $m$ computes $g$} \\ \text{defined} & \text{if turing machine \$...