Questions tagged [halting-problem]
Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.
426
questions
-3
votes
1
answer
67
views
Can a decider return "Undecidable" on the Halting Problem? [closed]
So, I know there is no general algorithm for the halting problem, but I was curious if a three output decider could at least give us "an" output {0 if doesn't halt, 1 if halts, U if ...
0
votes
2
answers
51
views
Why there can't be two instances of a "reverse" program in the Halting problem?
So in the halting problem, there is a program that reverses the output of a program that tells if the input program halts or runs forever(I'll call it the main program further). The whole paradox is ...
- 101
-5
votes
2
answers
69
views
Halting Problem Question
Let HALT be a program that can decide the halting problem for any program and its input. HALT has two inputs, the program and the program's input.
Let OPPOSITE be a program that accepts a program as ...
1
vote
4
answers
3k
views
Can we ever achieve Turing completeness?
I want to relate Turing completeness to the Halting Problem.
As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. But ...
-4
votes
2
answers
44
views
Proof of halting problem
if we change the halts to do_not_halt() function, it works, so how can this be a proof?
def g():
if halts(g):
loop_forever()
if we change the halts to ...
0
votes
2
answers
51
views
Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof
all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct?
TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
- 1
-2
votes
4
answers
96
views
Can halting problem solved by soft computation?
As far as I know, the halting problem means we can't create a program that checks whether another program is stuck or halt based on given input. This means, the program expects two inputs and one ...
0
votes
0
answers
21
views
Reduce A ∶= {x ∈ N ∣ x < 10} to Halting Problem on empty tape
I am preparing for an exam in computability and still learning about the idea of reductions. I found an interesting problem to start with and am curious if my approach is correct:
Let H0 be the ...
- 1
0
votes
2
answers
63
views
Does exist an algorithm that decides whether a program halts or not as its timeout approaches to infinity?
By an algorithm $A(p, t)$ attempting to decide whether the program $p$ halts or not by running the program for $t$ seconds (the timeout) and trying to prove that it doesn't halt at the same time, can ...
- 11
3
votes
0
answers
179
views
Does this paper by Patrick Cousot describe an undecidable method for model checking?
All of the discussion is in the context of this paper.
I think that the whole procedure that the paper describes is not decidable, because if we can have an algorithm for it, then we can solve halting ...
- 31
0
votes
1
answer
42
views
Reduction from a language with unknown decidability to HALT
We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction
$$
L\leq_mHALT
$$
So that I can ...
- 1
-2
votes
2
answers
106
views
Can we tell if we can tell if an algorithm halts or not?
We proved that, there exist no algorithm so it can tell us if an algorithm halts or not (a.k.a. the halting problem is undecidable). But it surely can handle some of those; can we tell which of those ...
- 11
0
votes
0
answers
47
views
Is game of life an example to halting problem?
I am working on a solution that can say if an initial composition is going to live forever or eventually die without calculating each generation until it reaches a stable or an ever-repeating cycle in ...
- 101
1
vote
0
answers
35
views
How much is decidability compromised within this restriction of the fixpoint combinator?
Though purely functional programming languages, such as Haskell, is commonly thought to have no side-effects, there is a caveat: Recursive calls may hang.
I considered this to be undesirable, and ...
- 313
1
vote
1
answer
62
views
Is the problem of Proper Subset of decidable languages decidable?
Given 2 recursive - decidable languages $L_1$ and $L_2$ is the problem $L_1 \subset L_2$ solvable - decidable?
Since both $L_1$ and $L_2$ are recursive - decidable there exist Turing Machines say $M_1$...
- 165
7
votes
1
answer
1k
views
What is the complexity of theorem proving?
I'm learning some computer science and mathematics by myself. I know that proving theorems in ZFC is undecidable in general, but, is there a formal way to express how complex it is? Is it as complex ...
1
vote
1
answer
30
views
Concrete example of a set with a lower degree of unsolvability
Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've ...
- 413
0
votes
1
answer
65
views
How is there a paradox in the halting problem when you can trace it and it's very clearly non-halting?
Here's Alan Turing's halting problem in pseudocode:
...
1
vote
3
answers
145
views
Halting problem unsolvability leads to a contradiction - where's the mistake?
You are all familiar with the halting problem so I won't repeat it.
Suppose $H$ is a Turing machine which takes as input an encoding of another Turing machine $M$, then searches all possible proof ...
- 1,685
0
votes
1
answer
196
views
Modify Turing’s proof of the undecidability of the halting problem
Modify Turing’s proof of the undecidability of the halting problem to show there is no Turing machine P with the following two properties:
For all Turing machines M, if M() accepts then P(⟨M⟩) ...
- 25
0
votes
1
answer
42
views
Is there a maximal set of programs that terminate?
It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem:
Is there a maximal decidable set of ...
- 103
0
votes
1
answer
70
views
Using undecidability to prove P != NP
Given the challenge of proving algorithmic bounds on the likes of 3-SAT to resolve P versus NP, I wondered whether it might be possible to use undecidability within an NP problem to ensure that we can ...
- 1
0
votes
0
answers
53
views
Reduction from Diophantine Equation Problem to Halting Problem
I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem.
Can you either explain it to me or give me a credible source from which I can ...
- 1
11
votes
3
answers
3k
views
Detecting if three Turing Machines halt given a magic oracle that is only used twice
We were given a question in class as follows:
You have a "magic oracle" that can decide if a Turing Machine halts. You have three TMs $T_1, T_2, T_3$. Device an algorithm that decides which ...
- 121
0
votes
0
answers
56
views
Is there a good example of computing a sequence that illustrates the Halting Problem?
I know that Busy Beaver problem can be used to illustrate the Halting Problem and it's probably the canonical problem used when talking about the Halting Problme . But long time ago I came across some ...
- 101
0
votes
1
answer
59
views
Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?
Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when ...
-3
votes
1
answer
82
views
Is there an unsound solution to the halting problem that makes the following functions computable?
I'm interested in this functions
\begin{align*}
g(m) &=
\begin{cases}
\text{defined} & \text{if turing machine $m$ computes $g$} \\
\text{defined} & \text{if turing machine $...
- 75
1
vote
1
answer
77
views
Efficiency of Halting Problem on finite space TMs
This question is about the (Edit: universal) Halting Problem on a TM with finite space.
The Halting Problem is obviously decidable on those TMs. So my question now is how efficient we can decide it.
...
- 119
-4
votes
1
answer
83
views
can you write a halting decider that is only wrong about itself by avoiding diagonalization?
in here they claim: "there is an algorithm deciding almost all instances of [halting problem]"
so I'm wonder whether there is a computable function $h':\mathbb{N}\to\{0,1\}$ such that the ...
- 75
-4
votes
1
answer
87
views
can you find an algorithm for this function?
consider the following function
$$
\begin{align*}
f(m,n) &=
\begin{cases}
k & \text{if program $m$ halts on input $n$ after $k$ steps} \\
m & \text{if program $m$ loops on ...
- 75
-2
votes
2
answers
217
views
Halting problem disproof
Introduction
This is a heavily updated question I have asked on this forum previously. I have understood and corrected the earlier errors and mistakes I made, and after doing that it still seems I ...
- 107
0
votes
1
answer
305
views
Does the halting problem belong to NP class of problems?
On the one hand it does not belong to NP problems because it simply is not solvable and is undecidable and on the other hand it is an NP problem because there are claims that it is NP-hard and ...
- 1
0
votes
0
answers
164
views
Halting problem reduction to single digit numbers
I'm thinking of the solution for severaly days, but I'm not sure about my solution is on the correct way.
I need to prove that the next problem is undecidable:
Input: An N program which requires an y ...
1
vote
1
answer
51
views
Is it possible to determine if a 0-arity function [a program with no input] will always terminate
The halting problem concerns programs which take input.
By framing the halting problem on the diagonal argument it is clear why this is so.
What about programs with no input, constant functions.
Can ...
- 141
0
votes
2
answers
94
views
Are there some programs for which the only proof of termination, is running of the program, and waiting to see if it stops, no matter how long?
The halting problem is semi-decidable, which means that if a program terminates then it will always be able to be determined.
Some programs can be proven to terminate without running them, with say:
...
- 141
1
vote
2
answers
87
views
Consequences of the Halting Problem
The halting problem is semi-decidable.
Does that mean that:
If a program terminates it can always be established/determined?
If a program does not terminate
It can sometimes be established/...
- 141
-4
votes
5
answers
397
views
Halting problem logic must be wrong
I think that I have found an issue with the proof of the halting problem, which would cause the entire proof to be invalid.
To ensure I understand, here is Turing's proof of the halting problem being ...
- 107
0
votes
1
answer
226
views
Are these functions computable?
consider $g$ and $f$ and $h$ as
$
\begin{align*}
g(m) &=
\begin{cases}
1 & if\;program\;m\;halts\;on\;input\;m \\
0 & otherwise \\
\end{cases}
\end{align*}
$
$
\begin{...
- 75
-4
votes
1
answer
411
views
Can you find a counter example for this sketch of a solution to the halting problem?
if we define halting problem as follows
$
\begin{align*}
h(m,n) &=
\begin{cases}
1 & \text{if program $m$ halts on input $n$} \\
0 & \text{otherwise} \\
\end{cases}
\end{...
- 75
0
votes
0
answers
107
views
proof that halting problem is undecidable
In the book Formal languages and automata by Peter Linz, 4th edition (Jones & Bartlett Learning), on pages 300-301,
there is a proof for the fact that the halting problem is undecidable.
The proof ...
- 89
1
vote
0
answers
38
views
Understanding unprovable halting, model theory, and (in)completeness
I know computability, but not model theory and logic, so this question may be naive or confused in that respect.
A blog post of Scott Aaronson mentions a Turing Machine $M^*$ such that the statement P:...
- 4,099
1
vote
1
answer
156
views
prove that there does not exist a Turing machine with a particular property
Prove that there does not exist a Turing machine M such that for every Turing machine K that halts on all inputs, $M$ accepts $\langle K\rangle$ if and only if $L(K)$ is infinite.
The above question ...
- 289
0
votes
2
answers
66
views
Why is $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ decidable?
I get that the argument for this set $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ to be decidable is that $|w|\leq7$ meaning it is a finite set and therefore it can be decided. ...
- 3
0
votes
0
answers
59
views
How should I imagine $M_w[\epsilon]\downarrow$ for the empty halting problem or $M_w[w]\downarrow$
I'm learning about computability problems e.g. reducing the general halting problem to the halting problem on a blank tape. But before I can understand this problem I first have to understand what ...
- 3
0
votes
1
answer
237
views
Is the set of Turing machines that halt on infinitely many inputs not recursively enumerable?
Consider this "generalized halting problem":
$$
GHP = \{<M>| \mbox{ there are infinitely many inputs that $M$ halts on}\}.
$$
I'd like to prove that $GHP\notin RE$, but it doesn't seem ...
- 3
0
votes
0
answers
35
views
Is this version of the halting problem NONELEMENTARY?
Input: A TM $M$ and an integer $k$.
Output: Yes if $M$ halts within $2\uparrow\uparrow k$ steps (where $\uparrow\uparrow$ is tetration (iterated exponentiation)).
Intuitively, it seems like this has ...
- 1
1
vote
1
answer
118
views
a halting turing machine
Prove that there does not exist a universal Turing machine that takes a pair $\langle M, w\rangle$ as input, where M is a Turing machine and w is a string, and that always halts, accepts if $M$ ...
- 289
0
votes
1
answer
121
views
Is there a Turing machine that packs a machine and its input into a single machine?
Let $U$ be the universal Turing machine. Is there a Turing machine $T$ taking two inputs such that $\forall m \forall n \exists q \; T(m; n) = q \land U(q;0)=U(m;n)$?
It seems "obvious" that ...
- 75
14
votes
5
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
465
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 ...
- 453