# Questions tagged [halting-problem]

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

315 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
557 views

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 ...
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 ...
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 ...
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)....
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 ...
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.....
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...