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

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

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

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