Questions tagged [halting-problem]
Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.
329
questions
2
votes
2answers
43 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
59 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
54 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
32 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
30 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 ...
0
votes
2answers
63 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
53 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 ...
0
votes
1answer
52 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
22 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
124 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
18 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}$ ...
1
vote
1answer
54 views
Existence of particular/specialized halting oracles
It is known that there does not exists an oracle $H$ which given any pair $(M,I)$ where $M$ is a machine and $I$ is an input (possibly still a machine) to have $H(M(I)) = YES$ if $M(I)$ halts and $H(M(...
0
votes
1answer
50 views
Faults in the halting problem reasoning
I find very interesting the problem of existence of a machine $H$ which given as input any algorithm $P$ outputs whether $P$ halts or not. Alan Turing disproved the existence of such an $H$ machine in ...
0
votes
1answer
38 views
Cryptosystems whose hardness depends on solving the halting problem?
There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.
This post Gives a list of some famous cryptosystems whose underlying ...
1
vote
2answers
70 views
Why do we proof the halting problem with turing machines?
It can be shown that Turing machines, Ī¼-recursive functions and reasonable programming languages can compute/decide the same problems. I wonder why we then still proof the halting problem with Turing ...
1
vote
1answer
37 views
Is Rice's Theorem equivalent to the Halting problem?
As I understand it Rice's Theorem seems to imply the existence of the Halting problem. That is, with Rice's Theorem, we can prove that the Halting problem is undecidable. However, to me, it seems like ...
0
votes
2answers
102 views
Is the halting problem pointless?
Some programs run quickly, some programs run slowly, and some spend all eternity whirring and whizzing without ever halting. The halting problem uses a thought experiment to prove that there cannot ...
0
votes
0answers
36 views
Turing machine M' from M
Let M be a Turing machine not necessarily halting on every input. Construct Turing machine Mā² which halts on w if ww ā L(M) and does not halt otherwise.
2
votes
1answer
46 views
Union of every language within group of decidable languages is also decidable?
So I was trying to solve following exercise:
Let $(L_{i})_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L_{i}$ is decidable. Then $\cup_{i \in \mathbb{N}}L_{i} $ is ...
0
votes
0answers
46 views
Why is it impossible to iterate over all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$?
Define $\{\sigma(n,k,m,i)\}_{i=1}^{l_m}$ an ordered set of all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$
There are $(2kn)^{kn}$ TMs with $n$ states and $k$ symbols, ...
1
vote
3answers
95 views
Are files download times actually unknowable due to the halting problem?
When downloading a file from the internet to our computer we are usually prompted with an estimate of how long it will take for the file to be downloaded.
From the Halting Problem, we know that $\...
0
votes
1answer
45 views
Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?
This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17}^c \subseteq \text{Goto}$. This language contains exactly ...
0
votes
1answer
58 views
Turing-completeness of Goto language with limited constants
This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17} \subseteq \text{Goto}$. This language includes exactly ...
0
votes
1answer
67 views
Confusion of halting problem
Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts.
lets P be program that determine one of the ...
0
votes
0answers
14 views
Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$
Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$?
1
vote
3answers
56 views
Halting problem vs. automated theorem proving?
In the Theory of Computation tutorial offered by Complexity Tree (I just began the 2nd video), it talks about how the Halting problem was developed to show that mathematics could not be automated. ...
0
votes
0answers
31 views
Can a pushdown automaton solve the halting problem for another Pushdown automaton?
Can a pushdown automaton solve the halting problem for another Pushdown automaton?
It's already shown here turing machine can solve the halting problem for a pushdown automaton.
Decidability of ...
0
votes
1answer
109 views
What's the complexity class of determing the halting problem of a finite memory Turing machine?
What's the complexity class of determining the halting problem of a finite memory Turing machine?
What is the computational complexity class of determining whether a machine halts on any input if it ...
-1
votes
1answer
43 views
Is it possible to construct a Turing Submachine such that a regular turing machine can decide whether the TSM halts but the TSM cannot [closed]
Is it possible to construct a not fully turing complete version of a turing machine such that a regular turing machine can solve the halting problem for the Turing Submachine but the Turing Submachine ...
0
votes
1answer
55 views
Semi-decidability of the language $\overline{L_{\epsilon}}$
Firstly consider the problem: given $L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. Assume for contradiction $\overline{L_{H}}$ is semi-decidable, then ...
1
vote
2answers
108 views
Do there exist coding languages where the halting problem is solvable but not trivial
Does there exist a coding language where
1. It is always possible to determine whether a computer program will halt or run forever. And
2. The answer is not always yes. (or always no)
So languages ...
2
votes
1answer
68 views
Under what kind of oracles are $P$ and $NP$ equivalent?
How strong have the oracles needed to be for these two classes to be proven equivalent with respect to them?
For instance: is $P^H$ = $NP^H$ (ie. is $P$ equipped with an oracle to solve the halting ...
1
vote
0answers
47 views
If a turing machine can't solve the halting problem for a machine X, does this imply that X is at least as powerful as a turing machine?
Say I have a deterministic machine X, and I prove that a turing machine can't solve the halting problem for this machine when given a certain input. Does this imply that this machine X is turing-...
0
votes
2answers
44 views
proving $E_{TM}$ is undecidable using the halting language
How to prove that:
$E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$
(is undecidable)
using the language:
$H_{halt}=\{(āØMā©,w):M\ halts\ on\ w\}$.
I tried to prove by ...
0
votes
0answers
42 views
Is the undecidability of a given problem undecidable?
Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
0
votes
1answer
33 views
How to build a TM which decides $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$
For a specific natural $k$ we define the language of couples $(\langle M \rangle, x)$ such that $M$ stops on $x$ and the couple's encoding is bounded by $k$ i.e $L_k := \{(\langle M \rangle ,x)\in HP :...
21
votes
6answers
3k views
Halting problem theory vs. practice
It is often asserted that the halting problem is undecidable. And proving it is indeed trivial.
But that only applies to an arbitrary program.
Has there been any study regarding classes of programs ...
2
votes
2answers
49 views
Zero-Sum Games and Halting Problem
Wikipedia states on the page of the halting problem, "For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to ...
0
votes
0answers
49 views
Can a halting configurations of a Turing Machine has the same state of another configuration has?
At first, I believed since the state a halting configuration is at will be a halting state, whenever a configuration goes into that state, the TM halts.
Hence, there should not exist two ...
0
votes
2answers
56 views
How could you “solve” the halting problem if, hypothetically, the busy beaver numbers were “small”?
I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.
I'm trying to figure out how you could ...
0
votes
2answers
24 views
Given an input and a program when can you derive the output faster than just running the program?
Given an input string W, a description of a turning machine M, and a target output string O (W,M,O) as input, when can a machine M' decide, in fewer steps than simply running M on W, if running M on W,...
1
vote
1answer
61 views
the problems that could exist if halting problem is solved
What problems might exist if halting problem is solved. If there exist an oracle that can compute whether a given machine halts or not then what would be problems that could exists if such oracle is ...
1
vote
1answer
51 views
How can we know if a Turing machine halts, given that it writes to finite memory?
I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine š
writes to an arbitrary amount of memory, and false if it ...
2
votes
1answer
60 views
Turing machines: can a machine write to a finite number of memory cells, but not halt?
I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it ...
0
votes
0answers
40 views
A Turing machine for which it is impossible to predict whether it halts or not on a fixed input
The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
0
votes
1answer
72 views
Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not
It is known that the halting problem is decidable for every fixed $M_0$ Turing machine and every fixed $w_0$ input.
My related question would be the following: is it true that for every fixed $M_0$ ...
2
votes
1answer
216 views
Halting problem for fixed Turing machine and fixed input
It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.
What if we fixed both the machine and the input? I.e., is it decidable for every ...
1
vote
1answer
77 views
Proving undecidability of HALT_tm by reduction
Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ ...
