Questions tagged [halting-problem]

Question 1

The set of non-halting (program, input) pairs is not recursively enumerable (not RE). Does this imply that there is no infinite sequence of algorithms (e.g., heuristics) whose limit could enumerate ...

Question 2

I was reading through the proof for the halting problem and saw that that the "pathological" program that makes program H return the wrong result needs to have H inside it, where H is a ...

Question 3

Suppose we have some subset $S$ of Turing machines with the property that, for every partial recursive function, at least one machine in $S$ computes that function. Question: for any such subset $S$, ...

Question 4

In title, $TM_1$, $TM_2$ and $TM_3$ are all turing machines. In book Computational Complexity: A Modern Approach by Sanjeev Arora et al, the proof of the non-computability of the HALTING problem is ...

Question 5

I have been studying Rice's Theorem, and I came across the following proof, which I am trying to understand in more detail: [Rice's Theorem] If $A$ is an index set --- $\neq \emptyset$ or $\mathbb{N}$ ...

Question 6

However given that Th can be constructed, we can construct a second machine Td1 such that : Td1(Ti , D.N. of Ti) = HALT if Ti does not halt on its own D.N. OR Ti=Td1 LOOP if Ti halts on its own D.N. ...

Question 7

I am currently trying to understand why some finite sets or problems are always decidable. For example, the halting problem on an empty tape is proven to be undecidable: $$H_0 = \{w \in \{0,1\}^* \mid ...

Question 8

I am trying to understand whether it is possible to construct a Turing Machine (TM) that accepts an input if and only if it halts on that input. My question is closely related to the halting problem. ...

Question 9

The languages are defined as such (for standard Turing machines and over $\{0, 1\}^*$: $$ L_3 \triangleq \{ (\langle M \rangle, x) \mid \text{$\forall M^\prime, [x\in L(M^\prime)] \lor [\langle M^\...

Question 10

I've seen several definitions and discussions on this topic, but I cannot find the exact definitions of "Nondeterministic Turing Machine (NTM) that halts on an input x" and "NTM that ...

Question 11

It's well-known that the language $A_{TM} = \{\langle M,w\rangle: \text{M is a turing machine that accepts w} \}$ is undecidable. There's a standard proof that's presented in Sipser's "...

Question 12

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

Question 13

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

Question 14

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

Question 15

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

Stack Exchange Network

Questions tagged [halting-problem]

Halting problem at the limit of infinite sequence of heuristics

Halting Problem with Restricted Input

A variant of the halting problem for subsets of Turing machines

How can I think about one statement that $TM_1$ uses $TM_2$ to compute $TM_3$?

Barry Cooper's Proof of Rice's Theorem

is this the false assumption in a proof of the undecidability of the halting problem?

Why are finite sets decidable?

Is it possible to reduce H_0 to A_0?

I know the following language is undecidable by reduction to HP bar. But how does it relate to L_EQ?

When does a Nondeterministic Turing Machine halt?

Diagonalisation in the proof of undecidability of the acceptance problem for Turing Machines

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

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

Undecidability of a language similar to the Halting Problem

Accelerating semidecision of halting problem

Hot Network Questions