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.

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 ...
Kindness's user avatar
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: ...
2080's user avatar
  • 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, ...
Elementary Proof Lover's user avatar
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 ...
Sanyo Mn's user avatar
  • 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 ...
Diode's user avatar
  • 1
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!
mikealexx's user avatar
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 ...
Slim Shady's user avatar
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 (...
rus9384's user avatar
  • 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 ...
rus9384's user avatar
  • 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 ...
joro's user avatar
  • 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 ...
Just Curious's user avatar
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 ∈ {...
sergio ospina's user avatar
2 votes
1 answer
72 views

Reducing from the complement of the Halting Problem

Consider the halting problem $HALT_{TM} = \{\langle M, w\rangle: M \text{ is a TM that halts on input } w\}$, and some undecidable Language $L$ of the form $L = \{\langle M\rangle: M \text{ does a ...
cassnx's user avatar
  • 21
-2 votes
1 answer
72 views

Is the "intersection" of the special Halting Problem with a language always undecidable?

I'm exploring the decidability characteristics of a particular language formed by the intersection of two languages, specifically in the context of the Halting Problem. The languages are defined as ...
Just Curious's user avatar
3 votes
1 answer
119 views

Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction

Let's say a Language L is NON-semi decidable and undecidable. Let's also take the Halting problem H, which is a semi decidable and undecidable language. Is it possible to reduce L to H in a many-one ...
sergio ospina's user avatar
1 vote
1 answer
62 views

How far out can one determine a program is halting?

Suppose we have a finite set of programs, say, something like every Turing machine with 2 states and 7 symbols. After running all of them for a very long time, we've narrowed it down to a small subset ...
Trev's user avatar
  • 296
-1 votes
4 answers
153 views

Can code "run forever" if it contains no loops?

Is it possible to write a piece of code that will run forever without using a loop?
Callum's user avatar
  • 115
-2 votes
1 answer
48 views

Does the Halting Problem Explain the Fermi Paradox?

The Fermi Paradox asks why we have not yet encountered other intelligent life given the high chance of intelligent life emerging. I recently had the following thought: Evolution shapes the behaviour ...
Josh's user avatar
  • 1
6 votes
2 answers
2k views

What does it mean to prove the halting problem is undecidable "using arithmetization"?

In version gamma of the ACM/IEEE/AAAI Computer Science Curricula 2023, on page 50, one of the illustrative learning outcomes for the "Computational Models and Formal Languages" section of ...
user164282's user avatar
0 votes
1 answer
70 views

A program that solves the Halting Problem for programs with N states

My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in general. ...
Vincenzo Buselli's user avatar
3 votes
1 answer
119 views

For which values of $k$ is a $k$-state-bounded version of the halting problem decidable?

This is related to my previous question: Do proofs of $HALT$'s undecidability make it clear that it's practically relevant? I made a mistake of leaving something implicit when I asked it; namely that ...
CuriosityScream's user avatar
0 votes
1 answer
95 views

Do proofs of $HALT$'s undecidability make it clear that it's practically relevant?

The proof of $HALT$'s undecidability usually goes like this: we assume the existence of a halting decider and incorporate it into a machine $D$ that takes a TM as input, runs it on its own encoding ...
CuriosityScream's user avatar
-3 votes
1 answer
89 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 ...
Daniel Stilman's user avatar
0 votes
2 answers
58 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 ...
YKY's user avatar
  • 101
-5 votes
2 answers
89 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 ...
StackUser20004's user avatar
1 vote
4 answers
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 ...
D Star Let's Explore's user avatar
-4 votes
2 answers
60 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 ...
user279163's user avatar
0 votes
2 answers
78 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 ...
boinka's user avatar
  • 1
-2 votes
4 answers
127 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 ...
Muhammad Ikhwan Perwira's user avatar
0 votes
0 answers
24 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 ...
dport's user avatar
  • 1
0 votes
3 answers
117 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 ...
sbh's user avatar
  • 51
3 votes
0 answers
192 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 ...
Senmorta's user avatar
0 votes
1 answer
53 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 ...
John's user avatar
  • 1
-2 votes
2 answers
122 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 ...
sbh's user avatar
  • 51
0 votes
0 answers
76 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 ...
Yağız Alp Ersoy's user avatar
1 vote
0 answers
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 ...
Dannyu NDos's user avatar
1 vote
1 answer
142 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$...
RookieCookie's user avatar
8 votes
1 answer
2k 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 ...
Otakar Molnár López's user avatar
1 vote
1 answer
36 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 ...
user6767509's user avatar
0 votes
1 answer
76 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: ...
Curious cat's user avatar
1 vote
3 answers
160 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 ...
Quitting Due To Antisemitism's user avatar
0 votes
1 answer
246 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⟩) ...
staz6's user avatar
  • 25
1 vote
1 answer
48 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 ...
timgo's user avatar
  • 113
0 votes
1 answer
86 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 ...
Brian's user avatar
  • 1
0 votes
0 answers
66 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 ...
Mgh's user avatar
  • 1
11 votes
3 answers
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 ...
lombardo2's user avatar
  • 121
0 votes
0 answers
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 ...
RubenLaguna's user avatar
0 votes
1 answer
147 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 ...
J Jackson's user avatar
-3 votes
1 answer
92 views

Is there an unsound solution to the halting problem that makes the following functions computable?

I'm interested in this functions \begin{align*} g(m) &= \begin{cases} \text{defined} & \text{if turing machine $m$ computes $g$} \\ \text{defined} & \text{if turing machine $...
raoof's user avatar
  • 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. ...
Ondolin's user avatar
  • 129

1
2 3 4 5
9