# Questions tagged [halting-problem]

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

451 questions
Filter by
Sorted by
Tagged with
1 vote
96 views

### set of words w such that M halts on w is decidable

I need to prove that the language following language is not turing-recognizable: $$\text{dec-haltTM} = \{ \langle M\rangle: \text{M is a TM and the set of words that M halts on is decidable}\}$$ I ...
• 111
28 views

### Proving Non-Semi-Decidability of Language L - Seeking Reduction Strategy

I'm working on a problem involving the language 𝐿 = { 𝑤 ∣ time𝑀𝑤 ( 𝑥 ) ≤ ∣ 𝑥 ∣ + 1 for all words  𝑥 }. The language consists of words 𝑤 where the Turing machine 𝑀𝑤 halts within ∣ 𝑥 ∣ + 1 ...
44 views

### Undecidability of a language similar to the Halting Problem

I would like to prove the undecidability of the following language $L$, closely related to the Halting problem: $$L:=\{w \mid M_w \text{ accepts a word of size }|w|\}.$$ It is obvious for unary ...
586 views

### Accelerating semidecision of halting problem

There is a naive semidecision algorithm for the halting problem: simply simulate the program and see if it halts. Is there an algorithm that is asymptotically faster? More precisely, suppose the naive ...
• 220
1 vote
1k views

### Do programs within which a computable function runs a random number of times always halt, as in the halting problem?

I need some clarification regarding if computer scientists say a program like: ...
• 135
1 vote
61 views

### If Halting is not recursive, then why is it that not every set of the form $\{M: \text{M is a Turing machine that does XXX}\}$ is not recursive?

Suppose I wish to find out whether $\{M: \text{M is a Turing machine that does XXX}\}$ is recursive, where $XXX$ can be anything about the Turing machine. I have a bad proof that proves that all such ...
• 13
1 vote
45 views

### Intuitive explanation/overview of non-looping non-termination proofs

Looping non-termination is intuitively easy to understand and demonstrate, by finding/showing a sequence of transformations that cycles back itself. Say, using the rewriting system: ...
• 191
37 views

### confusion with the proof of halting problem

From what I have seen on YouTube such as https://youtu.be/Kzx88YBF7dY?si=5j9tzjMFGCn3aCXW, We have: Halt: program x input ---> yes halt/ no halt and opposite : halt if Halt returns no halt, and, ...
1 vote
91 views

### What is the role of diagonalization in the proof of undecidability of the halting problem?

I'm trying to understand the proof of undecidability of the halting problem. Some resources give a short proof based on a proof by contradiction. There is no mention of diagonalization. But some ...
• 195
141 views

### Mapping Reduction from HALT?

I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
78 views

### Is $\{\langle \langle M\rangle, q\rangle\mid M(\varepsilon)$ enters state $q$ infinite times$\}$ not in RE?

I'm trying to use reduction $\overline{HP} \leq L$, but I just can't think of a way to do so. Any help would be appreciated!
53 views

### How do people working on the Busy Beaver function keep track of all the turing machines?

I'm a CS undergrad so forgive me if this question isn't formulated well. I got curious about the Busy Beaver function recently, and it got me wondering how all the n-state Turing machines are kept ...
• 101
25 views

### Effectively universal Turing machines and Turing-completeness?

An effectively universal Turing machine $T$ is a Turing machine for which there exists a recursive reduction $f$ such that $\forall A:U(A)=T(f(A))$, where $A, f(A)$ are finite sequences of symbols (...
• 1,966
40 views

### Undecidability of the exactly-1-in-k halting problem

The problem: Given $k>1$ Turing machines decide if for every possible input exactly one of them halts. Is this variant of halting problem undecidable? Intuitively, it seems that it must be not ...
• 1,966
1 vote
49 views

### What is wrong with this finite tape attack on the folklore proof of the halting problem?

Crank disclaimer: I don't doubt the undecidability of the halting problem, but one proof confuses me. We have seen this folklore proof of the halting problem on several occasions. Assume a HALTING ...
• 141
1 vote
38 views

### Decidability terms clarification

I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability. Decidable: A language $L$ (a set of strings) is decidable if ...
1 vote