# Questions tagged [halting-problem]

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

379 questions
Filter by
Sorted by
Tagged with
27 views

### is there a TM $T(m;n)=q$ where $\forall n \forall m \exists q\space T_q(0)=T_m(n)$?

as the title says: is there a TM $T(m;n)=q$ where $\forall n \forall m \exists q\space T_q(0)=T_m(n)$? in another words we are looking for a TM $T(m;n)$ that given a TM number $m$ and input of that TM ...
• 101
5k views

### Is it provably true/false that for a program, there exists a proof whether it halts or not?

A standalone statement of my question Given a program that takes no argument, we are interested in whether the program will eventually terminate. My question is this: Theoretically speaking, can we ...
• 188
160 views

### Disprove: if L is decidable then Prefix(L) is decidable

The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
• 456
1 vote
63 views

### Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?

An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
• 221
1 vote
62 views

### Why do PDAs always halt?

Can’t a PDA get stuck in a cycle of blank transitions? Should the implementation detect such cycles and do something about them? That seems quite complex to consider all the edge cases. Does the ...
• 161
1 vote
46 views

### $\mathrm{MON} = \{\langle M\rangle : \text{$M$is monotone}\}$ is undecidable

That's a question from a home assignment by T. Zur: Say that a Turing machine $M$ is monotone if it halts on every input, and if the length of $w$ is greater than the length of $w'$ then $M$ performs ...
• 117
1 vote
88 views

### Proving Undecidability of this Language

Consider the language $$L = \{\langle M \rangle \mid \text{\exists an input x, where |x|<i, such that M halts on x, but it takes at least j steps} \}$$ where $i$ and $j$ are fixed non-...
1 vote
69 views

50 views

### Prove that EXIST = {$<M>$:There exists a string $w ∈ Σ*$ such that $M$ halts on $w$} is undecidable

This is a question by my professor Z. Luria in my Computability course. My first approach was to try and prove it by contradiction, assuming that EXIST is decidable and using the algorithm that ...
• 117
1 vote
194 views

### The difference between halting and accepting in a Turing machine in this context

I've read some articles in this forum, e.g. there were professional claimed that a Turing machine does not accept a language but it recognizes it. I respect that but I found the phrase "a ...
• 11
73 views

### Can we meaningfully state for what proportion of possible programmes we can determine if they halt, do not halt, or wether it is still undetermined?

[My apologies, I am not a computer scientist, merely an interested amateur. I apologise if this question does not make sense, is a known result, or a duplicate] To quote Wikipedia: The halting ...
• 143
38 views

### Which abstract machine or language is exactly expressive enough to produce the computable functions?

I'm interested in software verification and therefore only interested in algorithms which always terminate in predictable amount of time and can determine whether the final result is expected or not, ...
• 143
24 views

### Could you solve co-RE problems with a halting oracle?

The halting problem is $RE$ complete. With an oracle for the halting problem could you decide problems in $co RE$ with an oracle for RE?
34 views

### If the time hierarchy theorem holds relative to every oracle, what about a halting(RE) oracle?

I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) ...
38 views

### Does proving undecidability implies that H is RE-Complete

If I want to show that H is RE-Complete is it enough to show it's undecidable? or should I prove something else alongeside? $H$ is the halting problem: $H = \{<p,x>|p \textit{ halts on } x\}$\
• 199
218 views

### Halting problem is undecidable proof-:

Confused with this proof. I will point my confusions here. what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is ...
• 47
115 views

### Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?

Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps? I've read the similar questions and answers such as here, but I wanted to ...
204 views

### Why REC languages is undecidable under emptiness and finiteness?

Membership problem of Recursive languages are decidable. My approach: Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it. For string $w,$ if $w ∈ L,$ then $M$ halts in ...
1 vote
66 views

### Number of inputs in undecidability proof of halting problem

So first, just to make sure that I understand the proof, here is the proof as I understand it: Take a program $H(x,y)$, which determines whether $x(y)$ will halt or not halt: if $x(y)$ halts then $H$ ...
• 11
1 vote
36 views

### What does it mean for an integer to belong to the halting problem?

I have come across the description of a function $F: \mathbb{N} \to \mathbb{N}$ where the function is defined one way for $n \in \mathcal{H}$ and another way for $n \notin \mathcal{H}.$ In this ...
1 vote
52 views

### Halting Problem - Arguments to Halting Checker Function

I'm trying to understand the Halting Problem. All the explanations I've seen state that the problem arises when passing a program to a halting check function along with itself as input. For example <...
1 vote
27 views

### How to reduce $\overline{K} \leq L$, or how to show semi-decidability of a given language?

I'm currently preparing for an exam and I'm having trouble to solve the following Questions. Let $w \in \{0,1\}^*$ and let $L$ be a language defined as follows L = \{w \mid \mathsf{time}_{M_w}(x) \...
• 279
43 views

### Where is the error in this logic for halting Turing machines?

Let $\mathbb{H}$ be the set of all Turing machines that halt on all inputs. Consider the following Turing machine $T$. On input $\langle S \rangle$ where $S \in \mathbb{H}$ (note that the angle ...
• 323
1 vote
53 views

### Question about the proof of the undecidability of the Halting Problem

From what I can see, the proof of the undecidability of the Halting Problem relies on a fairly basic self-referential paradox, the simplified version being (from Wikipedia): ...
• 11
79 views

### What is the original input for the halting question

I was reading about the halting problem recently, but I couldn't quite figure something out. We take $H(x,y)$ to be a program which works out if program $x$ with input $y$ halts, and $H_2(x,y)$ to be ...
• 11
76 views

### Help Understanding the Halting Problem

There are certain points about the halting problem that do not make sense to me. I couldn't seem to find a good breakdown of it that addresses my notes below. I was wondering if someone could ...
139 views

### Is this solution for the Turing's "halting" problem correct?

I think that Alan Turing's solution for the "halting" problem might be wrong. Turing's main premise is wrong, he assumed the only way to check whether a program halts is to run it. He didn't ...