Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [halting-problem]

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

1
vote
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 ...
1
vote
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 ...
6
votes
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 ...
18
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
2
votes
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. ...
0
votes
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 ...
0
votes
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: ...
7
votes
3answers
946 views

The 'directionality' of reductions?

I've been finding myself a bit confused with the direction of reductions used to show that certain languages are not recursive. For example, let us say we want to determine if the Halting Problem ($...
0
votes
0answers
271 views

Complement of halting problem Co-RE or non R.E [duplicate]

Can someone please tell me if complement of halting problem(L) is Co-RE or non R.E ? I think that it is Co-RE as L' (L complement) is R.E but everywhere its given non R.E
1
vote
1answer
210 views

Proving Blank-halt to be recursively enumerable through reduction to Halting problem

To prove the blank-halt problem is undecidable (does a given Turing machine halt on the empty input), it's a case of reducing the halting problem to the blank-halt problem and since the halting ...
1
vote
1answer
80 views

Confusion about reduction of $L=\{w_i | M_i\text{ halts on }w_i\}$ to Halting Problem or Diagonalization language?

I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable but not recursive just like the Halting Problem, but is it enough to say that if I can solve ...
1
vote
1answer
174 views

A reduction of $HALT_{TM}$ to $A_{TM}$

A widely used example of reductions, is a reduction of $A_{TM}$ to $HALT_{TM}$. How to show the opposite reduction, meaning of $HALT_{TM}$ to $A_{TM}$, if possible.
1
vote
1answer
335 views

How to calculate Kolmogorov Complexity if we have access to an Oracle for the HALT Problem

I try to solve the following exercise: We know that K (x), the complexity of Kolmogorov, is incomputable. Show how calculate it, if we have an oracle for the membership problem (or for the HALT ...
0
votes
0answers
104 views

Can there be an oracle that solves its own halting problem?

Since the same contradiction from the Turing machine is still there, we allow the oracle not always return an exact value, and say it solves the halting problem if the probability of returning "HALT" ...
1
vote
1answer
64 views

NTM's and the halting problem

It is often stated that nondeterministic Turing machines cannot recognize any more languages than ordinary Turing machines. In particular, it is stated that there is no NTM that can take as input a ...
1
vote
1answer
73 views

A slightly different version of the halting problem

I got stuck with a question and would like to have a little guidance for the solution. I need to prove that the next problem is undecidable: Input - A program Problem - Does the number of possible ...
1
vote
2answers
141 views

Is the below language Non R.E?

$L_0=\{\langle M,w,0\rangle\mid M \text{ halts on } w\}$ $L_1=\{⟨M,w,1⟩\mid M \text{ does not halts on } w\}$ Here $\langle M,w,i \rangle$ is a triplet, whose first component $M$ is an encoding of a ...
22
votes
1answer
2k views

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

I was watching the "Five Stages of Accepting Constructive Mathematics" by Andrej Bauer and he says that there is two kinds of proof by contradiction (or two things that mathematicians call proof by ...
-1
votes
1answer
120 views

Does the existence of the universe mean Chaitin's number is more than half?

This may be too philosophical for this stackexchange. Chaitin's constant $\Omega$ is the probability that a bitstring will halt when run on a universal Turing machine. It is uncomputable due to the ...
4
votes
1answer
160 views

Is it possible to solve the halting-after-$n$ steps problem more efficient than just execute $n$ steps?

The halting-after-$n$ steps problem may be defined as the question if a given turing machine halts after a maximum of $n\in\mathbb{N}$ steps. Is it theoretically possible to solve this problem in ...
1
vote
0answers
33 views

Formal invalidation of question about self-referential partial halting problem solver [closed]

How do you formally invalidate a question about the decidability of a partial halting problem solver that answers correctly with the following kind of input: Turing machines that don't use the partial ...
4
votes
1answer
287 views

Finite subsets of the Halting problem are decidable. Can I prove the correctness of Turing machines computing these subsets?

I am trying to wrap my hand around the undecidability proof of the Halting problem, and to me it really seems to be more of a proof about representation than decidability. Namely, the proof that some ...
7
votes
1answer
3k views

Why is the halting problem semi-decidable?

This is what is know about halting problem and semi-decidability :- Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x. A ...
4
votes
1answer
458 views

Halting problem with Proof of The Immerman-Szelepcenyi Theorem (knowledge of the theorem might not be necessary to clear my doubt)

So, I was reading this pdf on complexity theory. On page 18 pf pdf (Page 12 of book) The Immerman-Szelepcsenyi Theorem is mentioned with proof. The following lines are from the book : The idea is ...
1
vote
0answers
42 views

Computational models where halting problem is solvable

Are there computational models that can be considered useful for solving common programming problems, where it can be proven that computation will terminate for all possible inputs?
2
votes
2answers
217 views

determining whether a program halts or not

I have difficulty understanding the halting problem. I know that for all possible Turing machines and strings w, we don't have a Turing machine which can decide whether a TM M halts on input w.Now my ...
0
votes
1answer
113 views

Why is the undecidability of the Halting Problem useful? [duplicate]

My understanding: The Halting Problem is undecidable for a Turing Machine, and yet it is decidable for a linear bounded automaton (a Turing Machine with finite tape). The reason is that the only way ...
0
votes
1answer
171 views

Prove that there exists a machine which decides an infinite subset of halting problem

We already know that $H:=\{\langle M,w\rangle | M$ halts on $w\}$ is undecidable, then how can there possibly be a machine that decides any infinite subset of $H$?
1
vote
1answer
72 views

Halting problem under spatial restrictions

Let $A(n, B, d)$, $B(n, d)$ be a {Turing machine, random-access machine, C program} with finite tape (which I'm going to denote "Turing machine*" and "random-access machine*" respectively), $n \in \...
1
vote
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?
0
votes
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 ...
2
votes
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. ...
2
votes
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 ...
1
vote
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$ ...
2
votes
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, ...
2
votes
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 ...
0
votes
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 ...
3
votes
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 ...
1
vote
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 ...
6
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
3
votes
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 ...