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
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
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 $\...
user avatar
  • 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?
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 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?
user avatar
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) ...
user avatar
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\}$\
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
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 <...
user avatar
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) \...
user avatar
  • 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 ...
user avatar
  • 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): ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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> ...
user avatar
  • 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” ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
8