Questions tagged [halting-problem]
Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.
282
questions
2
votes
1answer
55 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
41 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
34 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 ...
0
votes
1answer
26 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
159 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
27 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
20 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 ...
2
votes
1answer
50 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
29 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
38 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
17 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
82 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
68 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
58 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
28 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
54 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 ...
2
votes
1answer
40 views
Concise Way To Specify The Space Of All Python Programs Under A Certain Size And Running Time?
Given the grammar of the Python language, is there a concise way to specify the space of all possible (and correct) Python programs?
To avoid the underlying halting problem, the specification would ...
5
votes
1answer
288 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
38 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
87 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
40 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
197 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
57 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
15 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
79 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 ...
2
votes
1answer
89 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 ...
-1
votes
2answers
164 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 ...
2
votes
1answer
98 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 ...
-3
votes
1answer
81 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 ...
-1
votes
1answer
61 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 ...
1
vote
1answer
66 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 ...
0
votes
1answer
57 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 ...
2
votes
1answer
70 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 ...
0
votes
0answers
29 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?
4
votes
2answers
108 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$ ...
2
votes
1answer
87 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 ...
2
votes
1answer
85 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 ...
2
votes
1answer
42 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) ?
4
votes
0answers
87 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 ...
-1
votes
1answer
59 views
Does solving all Halting problem instances 'in the limit' imply we solve an undecidable problem?
The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)...
3
votes
2answers
241 views
Enumerate over all halting Turing Machines?
I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the ...
1
vote
1answer
162 views
Counter Machine (Halting Problem)
How can we show that Halting Problem for one-counter additive machines is decidable ?
1
vote
1answer
74 views
Halting Problem, Typed Version: A Headache
After many years, I have been revisiting the venerable old Halting Problem and the self-referential / diagonalization “party trick” that shows that there is no Turing Machine able to solve it.
I was ...
0
votes
1answer
81 views
Would Schmidhuber's theories of everything be capable of performing hypercomputation?
Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of ...
2
votes
2answers
118 views
Is determining if a Turing machine runs in constant time decidable if one assumes it halts?
As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts?
The decision problem, more formally:
Given a Turing machine $M$ where it is assumed ...
0
votes
2answers
106 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 (...
0
votes
1answer
86 views
Why a TM with infinite states can decide the halting problem?
Assuming we have a model of TM with an infinite number of states.
The domain and range of the transition function are also infinite.
Given a description of a TM $M$ and a string $w$ how can we use the ...
1
vote
0answers
33 views
How to create model for a powerful language whose programs are guaranteed to terminate?
I'm creating a powerful regular expression matching system that can be augmented by adding small microprograms to deterministic finite automaton (DFA) states. The microprogram solves the big bang ...
1
vote
2answers
221 views
Recognizer for decidable language and words it doesn't halt on
Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
1
vote
1answer
201 views
How to prove that a problem is undecidable by using the Halting problem?
I cannot understand how to reduce the halting problem to a property to show that is undecidable.
For example, I have this property of a Turing Machine and I have to prove if it's recursive or not:
"...
