# Questions tagged [halting-problem]

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

258 questions
Filter by
Sorted by
Tagged with
0answers
22 views

### $L = \{ \langle M \rangle \mid M$ is a Turing machine and $\mathcal{L}(M)$ is decidable $\}$

$L = \langle M \rangle \mid M$ is a Turing machine and $\mathcal{L}(M)$ is decidable $\}$. How could I show this language is undecidable using the HALTing method? A language $L$ is undecidable if its ...
1answer
31 views

### Variations of the halting problem

Let $M$ be an arbitrary Turing machine and $w \in \{0, 1\}^{*}$ be a binary string. The language $\text{HALT} = \{\langle M, w \rangle : M ~\text{halts on input} ~w \}$ is undecidable by the famous ...
2answers
145 views

### The Halting problem proof is wrong?

First, let's see the pseudocode proof of halting problem: P(x) = run H(x, x) if H(x, x) answers "yes" loop forever else halt Then we have a ...
1answer
41 views

### Probabilistic halting problem

I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing ...
12answers
49k views

### Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia [article] correctly explains that a deterministic ...
2answers
96 views

### Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
1answer
54 views

### Halting problem in C++

The halting problem relies on the fluidity of Turing machines. That is, a string can represent a machine. Can you do the same for C++ on a modern computer? Let's see my first attempt. Let ...
1answer
62 views

### How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive?

I am trying to prove that the language $$L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\}$$ belongs to Co-RE but ...
1answer
60 views

### Is halts-if-valid decideable?

I have a suspicion that Turing's famous proof that the halting problem is undecidable may not prove exactly what people assume that it proves. It may only prove that it is possible to limit the ...
1answer
36 views

### Reduction to proof undecidability of the problem: machine M and N accept infinitely many words

I am struggling with the following problem: Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and ...
1answer
50 views

### How can I write a genetic programming algorithm, given that the Halting problem is unsolvable?

I am learning genetic programming and to practice I want to write a simple algorithm which evolves a program that solves a simple function (say, square root). I intend to represent programs as ...
0answers
27 views

### Is Halting problem only applicable to infinite languages

Is the halting problem, only applicable for infinite languages? I assume that if the language is finite, then we can search over all words?
2answers
56 views

### Can every Turing Machine be translated into a SAT formula?

For the proof of "Cook-Levin Theorem", for a Turing Machine $M$ that accepts a language $L \in NP$ and input $x \in \{0,1\}^*$, we can create a SAT Formula, that is satisfiable if and only if $M$ ...
1answer
66 views

### Is the halting problem solvable for NPDAs?

After the total silence in response to my last question, I am rethinking my assumptions. DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my ...
1answer
51 views

### Show that the following language is undecidable

$\{ M \mid M \text{ is a machine that runs in }100n^3 + 300\text{ time }\}$ I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first ...
1answer
29 views

### Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
0answers
68 views

### Detecting loops in NPDAs

I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it. I used to think that you could detect an infinite loop by meeting ...
1answer
43 views

### Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM. I had this problem on my exam. From my ...
3answers
5k views

### Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
1answer
54 views

1answer
201 views

### Prove if a property of a Turing Machine is decidable or not, how can I do it?

I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not. For example, if a have this: (1.1) "M always halts within 100 steps" or this (1.2) "M recognizes ...
0answers
23 views

### Is there an impossibility to mechanically distinguish between sets and classes?

Assuming only computable functions, and in line with set theory, defining a "proper class" as a collection that is itself not allowed to be a member of a set. A "collection" is then defined as either ...
1answer
23 views

### does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence?

let S be the set of all programs that take a natural number as input and return another natural as output. let M be the set of all programs that take a natural number as input and return true or false....
1answer
327 views

### Is Alan Turing's proof of the incomputability of halting problem invalid?

I fail to see a contradiction in the halting machine proposed by Alan Turing. Definition of halting machine Where H = all possible programs that terminates N = all possible programs that do not ...