# Questions tagged [halting-problem]

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

426 questions
Filter by
Sorted by
Tagged with
67 views

### Can a decider return "Undecidable" on the Halting Problem? [closed]

So, I know there is no general algorithm for the halting problem, but I was curious if a three output decider could at least give us "an" output {0 if doesn't halt, 1 if halts, U if ...
51 views

### Why there can't be two instances of a "reverse" program in the Halting problem?

So in the halting problem, there is a program that reverses the output of a program that tells if the input program halts or runs forever(I'll call it the main program further). The whole paradox is ...
69 views

### Halting Problem Question

Let HALT be a program that can decide the halting problem for any program and its input. HALT has two inputs, the program and the program's input. Let OPPOSITE be a program that accepts a program as ...
1 vote
3k views

### Can we ever achieve Turing completeness?

I want to relate Turing completeness to the Halting Problem. As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. But ...
44 views

### Proof of halting problem

if we change the halts to do_not_halt() function, it works, so how can this be a proof? def g(): if halts(g): loop_forever() if we change the halts to ...
51 views

### Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct? TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
96 views

### Can halting problem solved by soft computation?

As far as I know, the halting problem means we can't create a program that checks whether another program is stuck or halt based on given input. This means, the program expects two inputs and one ...
21 views

### Reduce A ∶= {x ∈ N ∣ x < 10} to Halting Problem on empty tape

I am preparing for an exam in computability and still learning about the idea of reductions. I found an interesting problem to start with and am curious if my approach is correct: Let H0 be the ...
63 views

### Does exist an algorithm that decides whether a program halts or not as its timeout approaches to infinity?

By an algorithm $A(p, t)$ attempting to decide whether the program $p$ halts or not by running the program for $t$ seconds (the timeout) and trying to prove that it doesn't halt at the same time, can ...
179 views

### Does this paper by Patrick Cousot describe an undecidable method for model checking?

All of the discussion is in the context of this paper. I think that the whole procedure that the paper describes is not decidable, because if we can have an algorithm for it, then we can solve halting ...
42 views

### Reduction from a language with unknown decidability to HALT

We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction $$L\leq_mHALT$$ So that I can ...
106 views

### Can we tell if we can tell if an algorithm halts or not?

We proved that, there exist no algorithm so it can tell us if an algorithm halts or not (a.k.a. the halting problem is undecidable). But it surely can handle some of those; can we tell which of those ...
47 views

### Is game of life an example to halting problem?

I am working on a solution that can say if an initial composition is going to live forever or eventually die without calculating each generation until it reaches a stable or an ever-repeating cycle in ...
1 vote
35 views

### How much is decidability compromised within this restriction of the fixpoint combinator?

Though purely functional programming languages, such as Haskell, is commonly thought to have no side-effects, there is a caveat: Recursive calls may hang. I considered this to be undesirable, and ...
1 vote
62 views

### Is the problem of Proper Subset of decidable languages decidable?

Given 2 recursive - decidable languages $L_1$ and $L_2$ is the problem $L_1 \subset L_2$ solvable - decidable? Since both $L_1$ and $L_2$ are recursive - decidable there exist Turing Machines say $M_1$...
1k views

### What is the complexity of theorem proving?

I'm learning some computer science and mathematics by myself. I know that proving theorems in ZFC is undecidable in general, but, is there a formal way to express how complex it is? Is it as complex ...
1 vote
30 views

### Concrete example of a set with a lower degree of unsolvability

Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've ...
65 views

### How is there a paradox in the halting problem when you can trace it and it's very clearly non-halting?

Here's Alan Turing's halting problem in pseudocode: ...
1 vote
145 views

### Halting problem unsolvability leads to a contradiction - where's the mistake?

You are all familiar with the halting problem so I won't repeat it. Suppose $H$ is a Turing machine which takes as input an encoding of another Turing machine $M$, then searches all possible proof ...
196 views

### Modify Turing’s proof of the undecidability of the halting problem

Modify Turing’s proof of the undecidability of the halting problem to show there is no Turing machine P with the following two properties: For all Turing machines M, if M() accepts then P(⟨M⟩) ...
42 views

### Is there a maximal set of programs that terminate?

It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem: Is there a maximal decidable set of ...
70 views

### Using undecidability to prove P != NP

Given the challenge of proving algorithmic bounds on the likes of 3-SAT to resolve P versus NP, I wondered whether it might be possible to use undecidability within an NP problem to ensure that we can ...
53 views

### Reduction from Diophantine Equation Problem to Halting Problem

I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem. Can you either explain it to me or give me a credible source from which I can ...
3k views

### Detecting if three Turing Machines halt given a magic oracle that is only used twice

We were given a question in class as follows: You have a "magic oracle" that can decide if a Turing Machine halts. You have three TMs $T_1, T_2, T_3$. Device an algorithm that decides which ...
56 views

### Is there a good example of computing a sequence that illustrates the Halting Problem?

I know that Busy Beaver problem can be used to illustrate the Halting Problem and it's probably the canonical problem used when talking about the Halting Problme . But long time ago I came across some ...
59 views

### Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?

Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when ...
82 views