Questions tagged [halting-problem]
Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.
307
questions
0
votes
1answer
57 views
Confusion of halting problem
Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts.
lets P be program that determine one of the ...
0
votes
0answers
13 views
Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$
Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$?
1
vote
3answers
44 views
Halting problem vs. automated theorem proving?
In the Theory of Computation tutorial offered by Complexity Tree (I just began the 2nd video), it talks about how the Halting problem was developed to show that mathematics could not be automated. ...
0
votes
0answers
17 views
Can a pushdown automaton solve the halting problem for another Pushdown automaton?
Can a pushdown automaton solve the halting problem for another Pushdown automaton?
It's already shown here turing machine can solve the halting problem for a pushdown automaton.
Decidability of ...
0
votes
1answer
33 views
What's the complexity class of determing the halting problem of a finite memory Turing machine?
What's the complexity class of determining the halting problem of a finite memory Turing machine?
What is the computational complexity class of determining whether a machine halts on any input if it ...
-1
votes
1answer
36 views
Is it possible to construct a Turing Submachine such that a regular turing machine can decide whether the TSM halts but the TSM cannot [closed]
Is it possible to construct a not fully turing complete version of a turing machine such that a regular turing machine can solve the halting problem for the Turing Submachine but the Turing Submachine ...
0
votes
1answer
39 views
Semi-decidability of the language $\overline{L_{\epsilon}}$
Firstly consider the problem: given $L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. Assume for contradiction $\overline{L_{H}}$ is semi-decidable, then ...
1
vote
2answers
93 views
Do there exist coding languages where the halting problem is solvable but not trivial
Does there exist a coding language where
1. It is always possible to determine whether a computer program will halt or run forever. And
2. The answer is not always yes. (or always no)
So languages ...
2
votes
1answer
61 views
Under what kind of oracles are $P$ and $NP$ equivalent?
How strong have the oracles needed to be for these two classes to be proven equivalent with respect to them?
For instance: is $P^H$ = $NP^H$ (ie. is $P$ equipped with an oracle to solve the halting ...
1
vote
0answers
39 views
If a turing machine can't solve the halting problem for a machine X, does this imply that X is at least as powerful as a turing machine?
Say I have a deterministic machine X, and I prove that a turing machine can't solve the halting problem for this machine when given a certain input. Does this imply that this machine X is turing-...
0
votes
2answers
35 views
proving $E_{TM}$ is undecidable using the halting language
How to prove that:
$E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$
(is undecidable)
using the language:
$H_{halt}=\{(āØMā©,w):M\ halts\ on\ w\}$.
I tried to prove by ...
0
votes
0answers
31 views
Is the undecidability of a given problem undecidable?
Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
0
votes
1answer
31 views
How to build a TM which decides $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$
For a specific natural $k$ we define the language of couples $(\langle M \rangle, x)$ such that $M$ stops on $x$ and the couple's encoding is bounded by $k$ i.e $L_k := \{(\langle M \rangle ,x)\in HP :...
20
votes
5answers
2k views
Halting problem theory vs. practice
It is often asserted that the halting problem is undecidable. And proving it is indeed trivial.
But that only applies to an arbitrary program.
Has there been any study regarding classes of programs ...
2
votes
2answers
34 views
Zero-Sum Games and Halting Problem
Wikipedia states on the page of the halting problem, "For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to ...
0
votes
0answers
25 views
Can a halting configurations of a Turing Machine has the same state of another configuration has?
At first, I believed since the state a halting configuration is at will be a halting state, whenever a configuration goes into that state, the TM halts.
Hence, there should not exist two ...
0
votes
2answers
44 views
How could you “solve” the halting problem if, hypothetically, the busy beaver numbers were “small”?
I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.
I'm trying to figure out how you could ...
0
votes
2answers
20 views
Given an input and a program when can you derive the output faster than just running the program?
Given an input string W, a description of a turning machine M, and a target output string O (W,M,O) as input, when can a machine M' decide, in fewer steps than simply running M on W, if running M on W,...
1
vote
1answer
43 views
the problems that could exist if halting problem is solved
What problems might exist if halting problem is solved. If there exist an oracle that can compute whether a given machine halts or not then what would be problems that could exists if such oracle is ...
1
vote
1answer
36 views
How can we know if a Turing machine halts, given that it writes to finite memory?
I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine š
writes to an arbitrary amount of memory, and false if it ...
1
vote
1answer
57 views
Turing machines: can a machine write to a finite number of memory cells, but not halt?
I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it ...
0
votes
0answers
36 views
A Turing machine for which it is impossible to predict whether it halts or not on a fixed input
The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
0
votes
1answer
43 views
Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not
It is known that the halting problem is decidable for every fixed $M_0$ Turing machine and every fixed $w_0$ input.
My related question would be the following: is it true that for every fixed $M_0$ ...
2
votes
1answer
126 views
Halting problem for fixed Turing machine and fixed input
It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.
What if we fixed both the machine and the input? I.e., is it decidable for every ...
1
vote
1answer
29 views
Proving undecidability of HALT_tm by reduction
Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ ...
3
votes
1answer
49 views
Help with finding a flaw in argument simulating large Turing machines with smaller ones
I have an argument which, if it goes through, just about proves that either:
Programming languages are more powerful than Turing machines
The busy beaver function ($BB()$) on Turing machines is ...
2
votes
1answer
79 views
Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$?
The halting problem states that there is no Turing machine that can determine whether an arbitrary Turing machine halts on $\epsilon$. But I try to ask something different, can we find a specific ...
-1
votes
1answer
46 views
Are non halting programs not computable?
Are non halting programs not computable? How are these two sets of programs related: is a non halting program just a specific example of a type of program that is not computable or is it technically ...
1
vote
1answer
44 views
Union of halting-like problem and non-halting-like problem
I came across the following problem:
Define languages $L_0$ and $L_1$ as follows :
$L_0=\{āØM,w,0ā©ā£M\text{ halts on }w\}$
$L_1=\{āØM,w,1ā©ā£M\text{ does not halt on }w\}$
Here $āØM,w,iā©$ is a triplet, ...
0
votes
1answer
27 views
how is the set of undecidable programs related to the set of non-halting programs?
Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting?
Thanks!
3
votes
1answer
206 views
Undecidability of two Turing machines acting the same way on an input
So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this:
$M_1$ ...
0
votes
1answer
62 views
In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?
Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
1
vote
0answers
21 views
Proving Problems are Undecidable/ Semi decidable? E.g. Halting Problem, Membership Problem? [duplicate]
I am having issues finding similarities in different cases where a problem such as the Halting Problem or the Accept-Ī problem is reduced to the Membership problem to prove that it is semi-decidable ...
1
vote
1answer
55 views
TM1 accepts w1 vs TM1 halts on w1
What is difference between following two problems, their decidability and recognizability status:
Given Turing Machine TM "accepts" given string w.
Given Turing Machine TM "halts on" given string w.
...
0
votes
1answer
36 views
is the empty language L = ā a subset of every languages?
I need to show false the following claim
Every language L which is a subset of $A_{TM}$ ($L \subseteq A_{TM}$) is undecidable.
For this, I wish to use the empty language L = ā
(I know is decidable)...
0
votes
2answers
88 views
if A is decidable then B is decidable too
Assume that a language A is reducible to language B. The claim is true?
if A is decidable then B is decidable too.
The correct answer is:
This claim is wrong. If A is e.g. the empty language (...
1
vote
1answer
21 views
Is checking if the length of a C program that can generate a string is less than a given number decidable?
I was given this question:
Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable?
With respect to ...
2
votes
3answers
154 views
Are there any problems that reduce to the halting problem?
I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where ...
0
votes
1answer
139 views
Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs
Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...
0
votes
1answer
65 views
How can Turing complete machines exist theoretically if the halting problem is undecidable
As the question says, if I input on the tape of a Turing complete machine a program that solves the halting problem with the correct inputs the program will never end its execution regardless of ...
0
votes
1answer
36 views
On the computable function of a problem that halts
Let's say program $P$ with given input $i$ is found to halt (or doesnāt halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ ...
0
votes
0answers
56 views
Why do intuitionists accept the nonconstructive proof that the halting problem is undecidable? [duplicate]
On the intuitionism page at Stanford Encyclopedia of Philosophy (SEP), it's said in Section 3.3 that
Because of the finiteness of a natural number in contrast to, for example, a real number, many ...
5
votes
1answer
293 views
How to write a coterminating, effectful program?
[Using Idris for code examples and terminology, but the question is not about Idris per se]
In a post titled A Neighborhood of Infinity, @sigfpe argues that "the kind of open-ended loop we see in ...
0
votes
1answer
42 views
I want to know where there is the flaw in my argument
I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable.
$L: \{\langle M\rangle: M\space is\space a\space TM\space and\...
-1
votes
1answer
121 views
Why is it not possible to prove that two Turing Machines calculate the same function?
I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?
0
votes
2answers
45 views
Busy-Beaver-like question for WHILE-Programs (Theoretical CS)
So this is exam-task is called "Busy WHILE-Programs"
In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:
...
1
vote
0answers
239 views
Proof by reduction and Turing machines [closed]
This is a practice question I have, but I can't wrap my head around it.
.............
Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}.
B = Blank Position
the ...
0
votes
0answers
60 views
What Makes A TM undecidable (using Recursion Theorem)
PROOF :We assume that Turing machine H decides ATM for the purpose of
obtaining a contradiction. We construct the following machine B.
B =āOn input w:
Obtain, via the recursion theorem, ...
0
votes
0answers
16 views
Given we restrict the time and memory allowed what bounds can we place on a halting decider?
If a program is given as much memory and as much time to execute as it wants, then the halting problem is undecidable, and by Rice's theroem all non-trivial, semantic properties of programs like that ...
1
vote
2answers
84 views
Since the halting problem is undecidable, does that mean that there exists an always undecidable program?
The usual demonstration of the halting problem's undecidability involves positing an adversarial machine (call it $A_0$) that runs the decider machine (call it $D_0$) on itself and performs the ...
