Questions tagged [halting-problem]
Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.
379
questions
0
votes
0
answers
27
views
is there a TM $T(m;n)=q$ where $\forall n \forall m \exists q\space T_q(0)=T_m(n)$?
as the title says:
is there a TM $T(m;n)=q$ where $\forall n \forall m \exists q\space T_q(0)=T_m(n)$?
in another words we are looking for a TM $T(m;n)$ that given a TM number $m$ and input of that TM ...
- 101
14
votes
6
answers
5k
views
Is it provably true/false that for a program, there exists a proof whether it halts or not?
A standalone statement of my question
Given a program that takes no argument, we are interested in whether the program will eventually terminate. My question is this:
Theoretically speaking, can we ...
- 188
2
votes
1
answer
160
views
Disprove: if L is decidable then Prefix(L) is decidable
The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
- 456
1
vote
1
answer
63
views
Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?
An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
- 221
1
vote
0
answers
62
views
Why do PDAs always halt?
Can’t a PDA get stuck in a cycle of blank transitions?
Should the implementation detect such cycles and do something about them? That seems quite complex to consider all the edge cases.
Does the ...
- 161
1
vote
1
answer
46
views
$\mathrm{MON} = \{\langle M\rangle : \text{$M$ is monotone}\}$ is undecidable
That's a question from a home assignment by T. Zur:
Say that a Turing machine $M$ is monotone if it halts on every input,
and if the length of $w$ is greater than the length of $w'$ then $M$
performs ...
- 117
1
vote
1
answer
88
views
Proving Undecidability of this Language
Consider the language
$$L = \{\langle M \rangle \mid \text{$\exists$ an input $x$, where $|x|<i$, such that $M$ halts on $x$, but it takes at least $j$ steps} \}$$ where $i$ and $j$ are fixed non-...
1
vote
1
answer
69
views
On the language of Turing machines that accepts 1 but does not accept 0
I need to find the find the minimal
class $\mathcal{L}$ belongs to where
$$\mathcal{L} = \{\langle M \rangle: M \text{ is a TM that accepts 1 but does not accept 0}\}.$$
I think I can prove that $\...
- 55
0
votes
1
answer
31
views
Memory capacity of Turing Machine Halting Problem
In Turning Machine Halting Problem, is the memory of the Turing Machine infinite or finite?
Does the Turing Machine have access to infinite tape? Or limited tape?
-2
votes
1
answer
124
views
Halting problem. Decider “recognising itself” in the input? Part 2
This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in ...
1
vote
1
answer
62
views
Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable
Yet another question from an exe. in the Computability class taught by Z. Luria -
I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable?
I mean we ...
- 117
4
votes
2
answers
112
views
Do all Turing-complete programming languages have to contain infinite loops?
Intuitively, it seems that if a programming language is Turing-complete, then it must contain a program that's an infinite loop. I have formalized this below:
Conjecture. There does not exist a set $...
0
votes
1
answer
50
views
Prove that EXIST = {$<M>$:There exists a string $w ∈ Σ*$ such that $M$ halts on $w$} is undecidable
This is a question by my professor Z. Luria in my Computability course.
My first approach was to try and prove it by contradiction, assuming that EXIST is decidable and using the algorithm that ...
- 117
1
vote
3
answers
194
views
The difference between halting and accepting in a Turing machine in this context
I've read some articles in this forum, e.g. there were professional claimed that a Turing machine does not accept a language but it recognizes it. I respect that but I found the phrase "a ...
- 11
4
votes
1
answer
73
views
Can we meaningfully state for what proportion of possible programmes we can determine if they halt, do not halt, or wether it is still undetermined?
[My apologies, I am not a computer scientist, merely an interested amateur. I apologise if this question does not make sense, is a known result, or a duplicate]
To quote Wikipedia:
The halting ...
- 143
0
votes
1
answer
38
views
Which abstract machine or language is exactly expressive enough to produce the computable functions?
I'm interested in software verification and therefore only interested in algorithms which always terminate in predictable amount of time and can determine whether the final result is expected or not, ...
- 143
0
votes
1
answer
24
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?
- 99
0
votes
1
answer
34
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) ...
- 99
0
votes
1
answer
38
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\}$\
- 199
-2
votes
1
answer
218
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 ...
- 47
2
votes
1
answer
115
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
1
answer
204
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
1
vote
1
answer
66
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$ ...
- 11
1
vote
1
answer
36
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 ...
- 13
1
vote
2
answers
52
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 <...
- 255
1
vote
0
answers
27
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) \...
- 279
0
votes
2
answers
43
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 ...
- 323
1
vote
2
answers
53
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):
...
- 11
-1
votes
2
answers
79
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 ...
- 11
2
votes
1
answer
76
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 ...
- 21
-3
votes
2
answers
139
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 ...
- 103
5
votes
1
answer
121
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 ...
user139273
0
votes
1
answer
29
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 ...
- 1
4
votes
1
answer
80
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
3
answers
331
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?
A Simulating Halt Decider (SHD) computes the mapping from its input to its own accept or reject state based on whether or ...
- 123
-6
votes
1
answer
290
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, ...
- 123
0
votes
1
answer
373
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
1
answer
408
views
Could H correctly decide that P never halts?
Because a halt decider must compute the mapping from its inputs to an accept or reject state on the basis of the actual behavior of its actual inputs, when H is a simulating halt decider H(P,P) would ...
- 123
2
votes
0
answers
54
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-...
- 10.8k
0
votes
1
answer
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 ...
- 101
0
votes
1
answer
46
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> ...
- 11
1
vote
1
answer
79
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” ...
- 13
0
votes
1
answer
22
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 ...
- 129
0
votes
1
answer
116
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 ...
- 3
0
votes
0
answers
17
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 ...
- 3
21
votes
3
answers
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 ...
- 375
0
votes
1
answer
87
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 ...
- 25
0
votes
1
answer
71
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 ...
- 43
3
votes
1
answer
157
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 ...
- 171
0
votes
1
answer
119
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 ...
- 349