Questions tagged [halting-problem]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
77 views

Does the undecidability of the halting problem require Turing Machines to be enumerable?

I (think I) understand the enumeration and then diagonalization proof of the undecidability of the halting problem, but I came cross this proof in SICP below, which does not seem to require the ...
1
vote
1answer
172 views

Prove that $H$ reduces to $H\varepsilon$

I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem). I am very confused how to PROVE it, I mean it is clear that we can ...
3
votes
1answer
557 views

Can a weaker version of the Halting Problem be solved?

I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this: Assume that some machine $...
1
vote
2answers
167 views

Is the halting problem theorem really proven

Here is a popular proof of the halting problem theorem: Suppose there exist a procedure h(x, y) so that for any procedure p(x) and any data d, the execution of h(p, d) will halt, where halt means ...
0
votes
1answer
36 views

How to proof HALT doesn't reduce to L?

What method(s) can I use in general to proof HALT doesn't reduce to given language?
3
votes
1answer
86 views

The halting problem for laymen [duplicate]

This line from Wikipedia made me want to ask this question: There is, however, no general procedure for determining whether an expression involving looping instructions will halt, even when humans ...
2
votes
1answer
105 views

How strong “Consistent Guessing Problem” is?

I saw "Rosser’s Theorem via Turing machines" at: https://www.scottaaronson.com/blog/?p=710 The modified halting problem (Consistent Guessing Problem) CGP is used in the proof: ...
0
votes
0answers
27 views

Prove that a language is undecidable by reducing HALT to it [duplicate]

Let $L = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} \textrm{x is the only string accepted by}\mathrel{}M_\alpha \right\}$ and $HALT = \left\{ \langle \alpha, x\rangle \mathrel{}...
0
votes
1answer
856 views

Are the implications of the diagonalization language different from those of the halting problem? [duplicate]

Revised: In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing ...
1
vote
1answer
1k views

How does reducing the Halting problem prove the reduction cannot exist?

For example, take the problem "Does M Halt on the Blank Tape?". My approach was to reduce the halting problem to prove this problem is also undecidable. I generated a Mw by Writing w on the tape ...
14
votes
5answers
4k views

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

I have the problem: Show that there exists a real number for which no program exists that runs infinitely long and writes that number's decimal digits. I suppose it can be solved by reducing ...
0
votes
2answers
53 views

What does the halting problem mean for a Babbage machine?

I read that the Babbage machine is Turing complete. Which means that no decision Turing machine will halt on the question "does the Babbage machine computes the logarithms of its input?" (for example)....
15
votes
5answers
4k views

Turing machine + time dilation = solve the halting problem?

There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer ...
0
votes
0answers
154 views

how to prove that the diagonal language K is r.e

To prove that K= $\{x \mid \phi_x(x)$ halts and accepts$\}$ is r.e.: we can recognize K by: for any x, we simply run x on machine $\phi_x$ and accept if the machine accpets else reject and that's it.....
0
votes
0answers
80 views

How to properly reduce a set of TMs to the halting problem?

Consider a standard enumeration of Turing machines ($T_0, T_1, T_2$, ...). Then, let language A be defined as $A = \{n \in\mathbb N | T_n(\lambda) \downarrow\}$. I need to reduce it to the halting ...
0
votes
1answer
319 views

how to mapping reduce any r.e. language to the diagonal language K?

We know that the halting problem $A_{TM}$ and the diagonal language K are mapping reducible to each other. Furthermore both are complete with respect to the mapping reduce relation. I would like to ...
1
vote
1answer
228 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
787 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 ...
19
votes
6answers
4k 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
635 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
50 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
1k 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
156 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
290 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
657 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. ...
1
vote
2answers
613 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
43 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
986 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
579 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
332 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
103 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 ...
2
votes
2answers
359 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
454 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
120 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
116 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
118 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
208 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
138 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
306 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
36 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
437 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 ...
8
votes
1answer
5k views

Why is the halting problem semi-decidable?

This is what is known about the halting problem and semi-decidability :- The 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. ...
4
votes
1answer
464 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
43 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
307 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
125 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
216 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 2
3
4 5
7