Questions tagged [halting-problem]
Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.
1
vote
2answers
45 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
28 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:
"...
0
votes
1answer
52 views
Halting problem with extra input
Can there be a function HALT(f, y) so that:
There are some x such that f(x) halts iff there ...
3
votes
2answers
93 views
Is it possible to write a program that calculates an algorithm's time complexity? [duplicate]
Title is self explanatory.
I have searched here on this site and haven't found any discussion about this.
Is it somehow related to Turing's Halting problem (which is undecidable)?
0
votes
1answer
37 views
Is this language recognizable?
Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable.
I don't think it's even recognizable, but I'm not sure. Regardless, I ...
0
votes
1answer
22 views
Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.
...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM.
I had this problem on my exam. From my ...
-1
votes
0answers
11 views
Proof that a language is not r.e. via reduction [duplicate]
I have to proof that the following language:
L:={ DTM | DTM halts for an infinite amount of inputs }
is not recursively enumerable.
Intuitively, I'd pick the ...
0
votes
0answers
24 views
Why do we need an opposite machine to prove that Acceptance problem is undecideable?
It is not clear why almost every book uses an opposite Turing machine to get a contradiction.
Here in slides they also use the Machine Dwhich simply outputs ...
4
votes
2answers
85 views
Converse of halting problem
It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is ...
3
votes
2answers
76 views
Does Halts reduce to all other undecidable languages?
In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of ...
2
votes
2answers
77 views
Why did Alan Turing have to define computation before demonstrating undecidability?
It seems to me that Turing could've just presented the following argument:
Theorem: Given a computational model $\mathcal{M}$ capable of conditional branching and indeterminate repetition the halting ...
1
vote
1answer
48 views
Prove if a property of a Turing Machine is decidable or not, how can I do it?
I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not.
For example, if a have this:
(1.1) "M always halts within 100 steps"
or this
(1.2) "M recognizes ...
1
vote
0answers
23 views
Is there an impossibility to mechanically distinguish between sets and classes?
Assuming only computable functions, and in line with set theory, defining a "proper class" as a collection that is itself not allowed to be a member of a set. A "collection" is then defined as either ...
1
vote
1answer
23 views
does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence?
let S be the set of all programs that take a natural number as input and return another natural as output. let M be the set of all programs that take a natural number as input and return true or false....
-3
votes
1answer
276 views
Is Alan Turing's proof of the incomputability of halting problem invalid?
I fail to see a contradiction in the halting machine proposed by Alan Turing.
Definition of halting machine
Where
H = all possible programs that terminates
N = all possible programs that do not ...
0
votes
2answers
112 views
Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable
I tried to prove by contradiction.
$L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable.
$$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, ...
4
votes
1answer
68 views
if an argument of a lambda only passes itself if it is further evaluated, is runtime always finite?
In order for a lambda expression to run forever, there must be at least one lambda in the expression
in which an argument is passed to itself. For example the following runs forever.
$$
(\lambda x.xx)...
8
votes
2answers
689 views
Halting Problem without self-reference: why does this argument not suffice (or does it)?
I'm trying to find a way to explain the idea of the Halting Problem proof in as accessible a manner as possible (to undergrad CS students). The simplest argument I have found is this one; this is ...
0
votes
0answers
26 views
Reduction of HP to L3
I want to make the following reduction:
HP is the Halting Problem: HP = {w#x | w, x ∈ {0,1}* , Mw halts on input x}
w is the binary coded turing machine Mw.
L3 is the problem which asks, if M ...
2
votes
1answer
68 views
What is the current state of the art in solving the halting problem? [closed]
Yes, I know it's uncomputable in the general case. What I want to know is what special cases have been solved, and if there is work ongoing on finding or developing more of them.
To be a little more ...
1
vote
1answer
45 views
Turing decider Halting Problem
Wiki and my classes Textbook defines a decider as:
In computability theory, a machine that always halts—also called a
decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a
Turing ...
1
vote
2answers
45 views
Does the undecidability of the halting problem require Turing Machines to be enumerable?
I (think I) understand the enumeration and then diagonalization proof of the undecidability of the halting problem, but I came cross this proof in SICP below, which does not seem to require the ...
1
vote
1answer
63 views
Prove that $H$ reduces to $H\varepsilon$
I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem).
I am very confused how to PROVE it, I mean it is clear that we can ...
3
votes
1answer
411 views
Can a weaker version of the Halting Problem be solved?
I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this:
Assume that some machine $...
1
vote
2answers
128 views
Is the halting problem theorem really proven
Here is a popular proof of the halting problem theorem:
Suppose there exist a procedure h(x, y) so that for any procedure p(x) and any data d, the execution of h(p, d) will halt, where halt means ...
0
votes
1answer
30 views
How to proof HALT doesn't reduce to L?
What method(s) can I use in general to proof HALT doesn't reduce to given language?
2
votes
1answer
46 views
The halting problem for laymen [duplicate]
This line from Wikipedia made me want to ask this question:
There is, however, no general procedure for determining whether an expression involving looping instructions will halt, even when humans ...
2
votes
1answer
56 views
How strong “Consistent Guessing Problem” is?
I saw "Rosser’s Theorem via Turing machines" at:
https://www.scottaaronson.com/blog/?p=710
The modified halting problem (Consistent Guessing Problem) CGP is used in the proof:
...
0
votes
0answers
24 views
Prove that a language is undecidable by reducing HALT to it [duplicate]
Let
$L = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} \textrm{x is the only string accepted by}\mathrel{}M_\alpha \right\}$
and
$HALT = \left\{ \langle \alpha, x\rangle \mathrel{}...
0
votes
1answer
117 views
Are the implications of the diagonalization language different from those of the halting problem? [duplicate]
Revised:
In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing ...
1
vote
1answer
226 views
How does reducing the Halting problem prove the reduction cannot exist?
For example, take the problem "Does M Halt on the Blank Tape?".
My approach was to reduce the halting problem to prove this problem is also undecidable. I generated a Mw by
Writing w on the tape
...
14
votes
5answers
4k views
How to prove the existence of a number which cannot be written by any algorithm?
I have the problem:
Show that there exists a real number for which no program exists
that runs infinitely long and writes that number's decimal
digits.
I suppose it can be solved by reducing ...
0
votes
2answers
41 views
What does the halting problem mean for a Babbage machine?
I read that the Babbage machine is Turing complete. Which means that no decision Turing machine will halt on the question "does the Babbage machine computes the logarithms of its input?" (for example)....
16
votes
5answers
4k views
Turing machine + time dilation = solve the halting problem?
There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer ...
0
votes
0answers
73 views
how to prove that the diagonal language K is r.e
To prove that K= $\{x \mid \phi_x(x)$ halts and accepts$\}$ is r.e.:
we can recognize K by: for any x, we simply run x on machine $\phi_x$ and accept if the machine accpets else reject and that's it.....
0
votes
0answers
37 views
How to properly reduce a set of TMs to the halting problem?
Consider a standard enumeration of Turing machines ($T_0, T_1, T_2$, ...).
Then, let language A be defined as $A = \{n \in\mathbb N | T_n(\lambda) \downarrow\}$.
I need to reduce it to the halting ...
0
votes
1answer
64 views
how to mapping reduce any r.e. language to the diagonal language K?
We know that the halting problem $A_{TM}$ and the diagonal language K are mapping reducible to each other. Furthermore both are complete with respect to the mapping reduce relation.
I would like to ...
1
vote
1answer
64 views
Does a DPDA halt on all inputs?
Given a deterministic DPA, is it possible to tell whether it halts on all possible inputs? Is this problem decidable?
The standard halting problem is "Given a DPDA and an input $x$, determine ...
1
vote
1answer
259 views
How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?
The language $\{w \mid w \in \{0,1\}^{*}\text{ and }M_w\text{ accepts infinitely many inputs}\}$ is undecidable, where $M_w$ is the Turing machine represented by $w$.
I am confused because I do not ...
6
votes
2answers
2k views
Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?
I have seen numerous proofs (such as this) that the Halting problem is in the class of NP. However, the Halting problem is non-computable.
Does it make sense to discuss the complexity of computing a ...
18
votes
6answers
3k views
Is halting problem computable for particular inputs/assumptions
From my understanding of the proof that halting problem is not computable, this problem is not computable because if we have a program P(x) which computes if the program x halts or not, we got a ...
1
vote
1answer
128 views
Reducing the infinite language problem to halting problem
Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $.
It is easy to show with Rices theorem that $INF$ is not decidable.
($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$).
How ...
0
votes
0answers
43 views
Is there a proof for the halting problem that does not involve an infinite nest of functions? [duplicate]
I have been doing a fair amount of research about the halting problem.
Most solutions I come across have the following pattern:
We assume we have a program H that solves the halting problem. We then ...
0
votes
0answers
84 views
Does halting problem apply to zero input or zero output algorithms?
We can prove that oracle does not exist by feeding it with copy of an algorithm and input to this algorithm and analyzing the output. What if there is no input or output? Can we still prove that ...
0
votes
0answers
37 views
Can machines of finite size ever solve their own halting problems?
A real-life computer can only store programs and inputs up to a certain length, which means that its halting problem can be solved with a lookup table. The most obvious way to represent this table ...
1
vote
2answers
307 views
reducing the halting problem to the blank tape problem
I have checked many discussions for understanding this problem.
I understand the reasoning , unfortunately there are some drawback in my understanding.
The Blank-tape halting Problem
Input: Turing ...
1
vote
1answer
139 views
Doubt with the halting problem undecidable proof
The Halting problem proof can be seen as the following programs:
Ends(P, I) is a program that detects (returns true or false) if the program P will halt or
not with the input I
Diag( P ): is a ...
0
votes
0answers
115 views
Need Help Understanding Proof by Contradiction for Halting Problem
I understand what the halting problem describes, but I do not understand how the proof by contradiction associated with it proves that it is impossible to solve.
The proof by contradiction can be ...
2
votes
2answers
275 views
Is the halting problem decidable by an “infinite Turing machine”?
It has been shown of course that the halting problem is undecidable. That is, we cannot formulate a Turing machine that will decide for any arbitrary turing machine whether it will halt or not.
...
0
votes
2answers
332 views
what is halting problem? [duplicate]
i have researched it on wikipedia and it produces me an unusual example and stories about Turing,so what i understand is if an program run in loop,an electronic device in cpu or in computer structure ...
