Skip to main content

# Questions tagged [halting-problem]

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

447 questions
Filter by
Sorted by
Tagged with
1 vote
1 answer
59 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
2 answers
42 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: ...
• 151
-2 votes
1 answer
35 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
1 answer
87 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
0 votes
1 answer
114 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 ...
0 votes
3 answers
77 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!
0 votes
0 answers
44 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
0 votes
0 answers
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,684
0 votes
1 answer
38 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,684
1 vote
1 answer
47 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
1 answer
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
1 answer
45 views

### Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

I need to prove if the following Language is or is not semi-decidable. A := {w ∈ {0,1}^* | there exists an input x on which M_w produces the output 0} Where A is the language of all the encoding w ∈ {...
2 votes
1 answer
72 views

• 73
1 vote
1 answer
84 views

### Efficiency of Halting Problem on finite space TMs

This question is about the (Edit: universal) Halting Problem on a TM with finite space. The Halting Problem is obviously decidable on those TMs. So my question now is how efficient we can decide it. ...
• 129