Questions tagged [halting-problem]
Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.
364
questions
-1
votes
0answers
60 views
Does the halting problem apply to a Dialetheistic logic(logic where a statement can be true, false or both) turing machine?
This hypothetical modification of a Turing machine would operate on balanced ternary, Dialetheist logic, which allows some controlled contradictions. In this logic a statement can have 3 values. False(...
0
votes
1answer
20 views
Could you solve co-RE problems with a halting oracle?
The halting problem is $RE$ complete. With an oracle for the halting problem could you decide problems in $co RE$ with an oracle for RE?
0
votes
1answer
32 views
If the time hierarchy theorem holds relative to every oracle, what about a halting(RE) oracle?
I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) ...
0
votes
1answer
29 views
Does proving undecidability implies that H is RE-Complete
If I want to show that H is RE-Complete is it enough to show it's undecidable? or should I prove something else alongeside?
$H$ is the halting problem: $H = \{<p,x>|p \textit{ halts on } x\}$\
-2
votes
1answer
75 views
Halting problem is undecidable proof-:
Confused with this proof. I will point my confusions here.
what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is ...
2
votes
1answer
86 views
Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?
Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?
I've read the similar questions and answers such as here, but I wanted to ...
0
votes
1answer
166 views
Why REC languages is undecidable under emptiness and finiteness?
Membership problem of Recursive languages are decidable.
My approach:
Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it.
For string $w,$ if $w ∈ L,$ then $M$ halts in ...
1
vote
1answer
32 views
Number of inputs in undecidability proof of halting problem
So first, just to make sure that I understand the proof, here is the proof as I understand it:
Take a program $H(x,y)$, which determines whether $x(y)$ will halt or not halt: if $x(y)$ halts then $H$ ...
1
vote
1answer
32 views
What does it mean for an integer to belong to the halting problem?
I have come across the description of a function $F: \mathbb{N} \to \mathbb{N}$ where the function is defined one way for $n \in \mathcal{H}$ and another way for $n \notin \mathcal{H}.$ In this ...
1
vote
2answers
48 views
Halting Problem - Arguments to Halting Checker Function
I'm trying to understand the Halting Problem. All the explanations I've seen state that the problem arises when passing a program to a halting check function along with itself as input. For example <...
1
vote
0answers
25 views
How to reduce $\overline{K} \leq L$, or how to show semi-decidability of a given language?
I'm currently preparing for an exam and I'm having trouble to solve the following Questions.
Let $w \in \{0,1\}^*$ and let $L$ be a language defined as follows
$$L = \{w \mid \mathsf{time}_{M_w}(x) \...
0
votes
2answers
40 views
Where is the error in this logic for halting Turing machines?
Let $\mathbb{H}$ be the set of all Turing machines that halt on all inputs. Consider the following Turing machine $T$. On input $\langle S \rangle$ where $S \in \mathbb{H}$ (note that the angle ...
1
vote
2answers
47 views
Question about the proof of the undecidability of the Halting Problem
From what I can see, the proof of the undecidability of the Halting Problem relies on a fairly basic self-referential paradox, the simplified version being (from Wikipedia):
...
-1
votes
2answers
75 views
What is the original input for the halting question
I was reading about the halting problem recently, but I couldn't quite figure something out. We take $H(x,y)$ to be a program which works out if program $x$ with input $y$ halts, and $H_2(x,y)$ to be ...
2
votes
1answer
56 views
Help Understanding the Halting Problem
There are certain points about the halting problem that do not make sense to me. I couldn't seem to find a good breakdown of it that addresses my notes below. I was wondering if someone could ...
-3
votes
2answers
119 views
Is this solution for the Turing's "halting" problem correct?
I think that Alan Turing's solution for the "halting" problem might be wrong.
Turing's main premise is wrong, he assumed the only way to check whether a program halts is to run it. He didn't ...
5
votes
1answer
114 views
Is halting problem for /// solvable assuming programs that maches the regex "^/[ab]*/[ab]*/[ab]*$"?
/// is an esoteric language, and I thought of posting a code-golf problem related to it.
A /// program of the form /p/q/r where p, q, and r are strings that do not ...
0
votes
1answer
24 views
Oracle for LBA halting on some input
Assume we have an oracle that tells, given a linear bounded automaton, if there exists an input on which it halts.
Can we then solve the real halting problem (i.e. decide if a given Turing machine ...
4
votes
1answer
72 views
Is there a $\Sigma^0_3$ variant of the halting problem?
In terms of the arithmetical hierarchy, the halting problem is known to be $\Sigma^0_1$-complete, and the so-called universal halting problem, is the problem of determining whether a given computer ...
-6
votes
3answers
266 views
Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?
Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?
This post requires reading the Linz proof at the end of this post first. Because ⊢* is defined to mean "an arbitrary ...
-6
votes
1answer
249 views
Halting problem undecidability and infinitely nested simulation
Halting problem: In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and
an input, whether the program will finish running, ...
0
votes
1answer
233 views
Proof that R (decidable languages) is not closed under homomorphism
After searching the internet for a bit, I found that the same proof came up over and over again.
The thing is, it seems like the proof is incomplete. Here's the proof:
However, the recursive ...
-5
votes
1answer
365 views
Could H correctly decide that P never halts?
Could H be adapted to correctly decide that P never halts?
See also: The Halting problem proof is wrong?
The standard pseudo-code halting problem template "proves" that the halting problem ...
2
votes
0answers
50 views
An approximation variant of the halting problem
It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable.
I have just thought of a variant approximation-...
0
votes
1answer
38 views
What is the strongest weaker version of the halts() function?
I was wondering about some questions related to the Halting problem. I might have not understood all the assumptions in it fully. Would you kindly help me, please?
I understand that the construction ...
0
votes
1answer
29 views
How can we solve halting problem efficiently?
I was doing exercises regarding the halting problem and there is this question where I am stuck
Ques: it goes like suppose if you can decide the halting problem with a query "Is <tm,s> ...
1
vote
1answer
66 views
Are run time bounds in P decidable when the problem is promised that an input program must halt?
I'm solving Problem 11-10(b) in "what can be computed".
11.10 Consider the decision problem HALTSINSOMEPOLY (HISP), defined as
follows.
The input is a program P, and the solution is “yes” ...
0
votes
1answer
21 views
Confusion in the added loop of the Halting Problem
I know there's like a thousand questions about this topic in the site and elsewhere. I'm just going to pick one that at least for me it serves as a good basis for my question. The answer by Rick ...
0
votes
1answer
56 views
Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"
Do two halting Turing machines accept the same language?
Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"):
Let M be an arbitrary Turing machine. Let ...
0
votes
0answers
14 views
Is the halting problem decidable for TMs that do not write to the tape? [duplicate]
Is the halting problem decidable for TMs that do not write to the tape?
Once a read only tape TM repeats a configuration, it will loop forever. Therefore, all we have to do to decide the above is ...
21
votes
3answers
5k views
Can a program exist that halts only if it can prove that it doesn't halt?
Consider a program P that enumerates possible proofs in some proof system and halts only if it finds a valid proof that P does not halt. Clearly no such proof exists, or the program would eventually ...
0
votes
1answer
78 views
How to prove (un)decidability
Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time ...
0
votes
1answer
32 views
Show that a language is not decidable by reducing from ATM
Let (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$)
show that the language L={<M1,M2,w> | M1 and M2 both accept or reject w} is undecidable by reducing
ATM ...
3
votes
1answer
128 views
Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?
Say I'm given an oracle that tells me whether or not $L(M)$, the set of words accepted by a Turing Machine $M$, is finite.
By leveraging this oracle, can I solve the halting problem? That is, on an ...
0
votes
1answer
88 views
Could the halting problem in theory be solved for any finite set of Turing Machines?
Suppose there's a program A that decides whether or not every program halts.
Then we could construct program B that invokes A and does the opposite. Do I halt? If so, loop. Do I loop? If so halt.
That ...
-1
votes
1answer
46 views
Issue with the Halting Problem
For clarity, I'll claim the supposed impossible program to be 'Code X'.
Something doesn't seem to make sense about the proof against Code X:
Consider a code that halts if you input oranges, but doesn'...
0
votes
0answers
42 views
halting problem vs watchdog
I have a theory that all finite state machines can be monitored by a second turing machine with infinite tape to determine if the state of the first machine was repeated thus reaching the conclusion ...
2
votes
2answers
65 views
State whether the language is in $R$, $RE$, etc. The intuition for the solution
I saw the solution but can't understand the intuition of the following question:
Let's define
$$L^{\ge k} = \{w\in L : |w| \ge k\}$$
and
$$L=\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^...
2
votes
2answers
305 views
Proving decidability
Regarding the following languages $L_1$ and $L_2$, I want to prove that $L_1$ is decidable and $L_2$ is undecidable. I want to construct a turing machine which can decide $L_1$ and reduce the halting ...
1
vote
1answer
67 views
Why is the common explanation to the halting problem an oversimplification?
So watching many youtube channels, the explanation to the impossibility of solving the halting problen involves assuming you can, doing the opposite, and feeding it back into itself to create a ...
1
vote
1answer
49 views
Is there a connection between the Undecidability Theorem and "software complexity"?
I was reading Complexity: The Emerging Science at the Edge of Order and
Chaos and a certain passage got me really intrigued. When discussing
Chris Langton's explorations of artificial life algorithms,...
2
votes
1answer
63 views
Halting (on empty input tape) for an infinite subset of all Turing machines
As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem.
But what if, instead ...
1
vote
2answers
124 views
Decidability of Turing machines and misconceptions on the halting problem
In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability ...
2
votes
1answer
91 views
What is the actual scope of the Halting Problem impossibility result?
Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function ...
1
vote
1answer
67 views
What is the contradiction in the proof of the halting theorem?
In the standard proof of the halting theorem, you are asked to assume that a TM_0() exists that takes another TM_1() and a string W and outputs whether TM_1() halts or executes forever right on string ...
1
vote
1answer
24 views
Uncertainty of coroutines writing to single socket
A program runs in a low-spec hardware utilizes coroutines writes to a single socket but how does the socket know when the data should be sent as there could more coroutines writing given N time.
I ...
4
votes
1answer
154 views
Kleene's Theorem and TMs
I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language?
Is this ...
0
votes
0answers
20 views
Other than correlation of events, what is the halting problem about?
Object B can be in two state 1(stopped), and 2(running) at an arbitrary time t in the future. Object A can be in two states x, and y at t0. However, if A is in state x, B must be in state 2 at t, and ...
0
votes
0answers
42 views
Can you write an algorithm that can generalize another algorithm?
Can you write an algorithm which can take in a given function/algorithm, and produce a distribution of generalizations of the function at hand? One such simple example of generalization might mean the ...
0
votes
0answers
25 views
Computability of a halting oracle for a specific class of machines
Let us consider the set of machines/algorithms with constant inputs (I would have preferred to say no inputs but I was told that every algorithm/machine has to have an input). We call $\mathcal{M}$ ...
