# Questions tagged [halting-problem]

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

249 questions
1answer
95 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 ...
1answer
444 views

### How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?

The language $\{w \mid w \in \{0,1\}^{*}\text{ and }M_w\text{ accepts infinitely many inputs}\}$ is undecidable, where $M_w$ is the Turing machine represented by $w$. I am confused because I do not ...
2answers
2k views

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

I have seen numerous proofs (such as this) that the Halting problem is in the class of NP. However, the Halting problem is non-computable. Does it make sense to discuss the complexity of computing a ...
6answers
3k views

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

From my understanding of the proof that halting problem is not computable, this problem is not computable because if we have a program P(x) which computes if the program x halts or not, we got a ...
1answer
254 views

### Reducing the infinite language problem to halting problem

Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \}$. It is easy to show with Rices theorem that $INF$ is not decidable. ($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$). How ...
0answers
44 views

### Is there a proof for the halting problem that does not involve an infinite nest of functions? [duplicate]

I have been doing a fair amount of research about the halting problem. Most solutions I come across have the following pattern: We assume we have a program H that solves the halting problem. We then ...
0answers
39 views

### Can machines of finite size ever solve their own halting problems?

A real-life computer can only store programs and inputs up to a certain length, which means that its halting problem can be solved with a lookup table. The most obvious way to represent this table ...
2answers
545 views

### reducing the halting problem to the blank tape problem

I have checked many discussions for understanding this problem. I understand the reasoning , unfortunately there are some drawback in my understanding. The Blank-tape halting Problem Input: Turing ...
1answer
142 views

### Doubt with the halting problem undecidable proof

The Halting problem proof can be seen as the following programs: Ends(P, I) is a program that detects (returns true or false) if the program P will halt or not with the input I Diag( P ): is a ...
0answers
192 views

### Need Help Understanding Proof by Contradiction for Halting Problem

I understand what the halting problem describes, but I do not understand how the proof by contradiction associated with it proves that it is impossible to solve. The proof by contradiction can be ...
2answers
424 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. ...
2answers
424 views

### 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 ...
1answer
38 views

### Looping through random integers - will it halt with probability 1?

Say I have a simple program that has the pseudocode like this: ...
3answers
946 views

0answers
39 views

### What portion of all possible turing machines halt?

Has anyone estimated Chaitin's constant for Turing machines with an empty tape as input?
3answers
95 views

### Is it possible to partially decide when will halt given any arbitrary input?

This is a problem that I think is a reduction from the halting problem. I have on two separate practice exams statements that, Given a Turing machine T and a string w, to determine whether T will ...
1answer
1k 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. ...
1answer
589 views

### Understanding the reduction of REGULARTM from ATM

REGULARTM is defined as below: REGULARTM ={〈M〉| M is a TM and L(M)is a regular language}. I am trying to understand the proof of REGULARTM being undecidable from ...
2answers
195 views

### A question about an input in a Halting Problem proof

Here is my Halting Problem proof, that largely mirrors other (non-diagonalizing) proofs that I've seen. $H(p,i)$ returns $1$ if program $p$ halts on input $i$. $H(p,i)$ returns $0$ if program $p$ ...
2answers
186 views

### Decidability of the halting problem on real-life finite computers given unlimited input

It has been my understanding that, technically, our computers are Finite State Machines. And, since FSMs halt when they run out of input, the halting problem is technically solvable. At some point, ...
1answer
97 views

### Showing $1$-reducibility of $\overline{\text{HALT}'}$ to index set

Note: overline denotes complement I am trying to show that $\overline{\text{HALT}'}\leq_1 \{i\colon\Phi_i=\Phi_e\}:= A$ for some fixed $e$ but I am misunderstanding the problem or method and can't ...
3answers
450 views

### What Turing's proof of Halting Problem really proves?

This is something that has bugged me for a while, so I hope you can help me. Suppose: $A'$ is the set of all programs, $halt?$ is the halting problem solver, $D$ is the program that is constructed ...
1answer
419 views

### Non recursively enumerable language proof by reduction to non-HP

I am trying to understand how the reduction proof for non r.e. languages works by following the examples from this website. In most cases to prove that a language is not r.e., you can reduce the ...
1answer
719 views

### Which Turing machine problems are Decidable?

Let $M_0$, $M_1$, $M_2$,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ? Given a natural number $N$, does $M_N$ starting with an empty ...
1answer
186 views

### Is there any demonstrably uncomputable concrete problem which does not rely on diagonalization?

So diagonalization as we all know is an extremely productive way of showing uncomputability, the other main tool used by CS people for this task being reduction. But it has occurred to me that I do ...
0answers
58 views

### Reducing Halting Problem to Acceptor for TM

We have $A_{TM}=\{(M,w)|M$ is a TM, $w\in \Sigma^*_{TM},M$ accepts $w\}$ We intend to show that $HALT(M,w)\leq_T A_{TM}$ i.e. if we are given a machine for $A_{TM}$, we can decide whether $M$ halts ...
0answers
26 views

### How did Turing prove that there is no general process to determine whether a Turing Machine is unsatisfactory?

In the book The Annotated Turing, Charles Pezold writes: Because Turing Machines are entirely defined by a Description Number, it might be possible to create a Turing Machine that analyzes these ...
1answer
299 views

### Under which operations is the class of non-recursive languages a closure?

I am currently studying turing computability and related problems such as the halting problem with a background in formal languages. I know that the class of recursive (decidable) languages is a ...
1answer
89 views

### Can we prove that a time machine is impossible using the Halting Problem?

Let us take a hypothetical machine i which halts on the ith day of the month if it rains on the ...