Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.
0
votes
0answers
21 views
A variant of the halting problem
Show that the problem of deciding, for a given TM $M$, whether $M$ halts for all inputs within $n^2$ steps ($n$ is the length of the input) is unsolvable. You can use the fact without proof that the ...
-1
votes
1answer
36 views
Complement of halting set is not r.e
suppose we don't know that Halting problem is not recursive.
I want to prove that complement of halting set is not r.e. then we can find halting problem is not recursive.
Can you direct prove that ...
4
votes
2answers
65 views
Is there an always-halting, limited model of computation accepting $R$ but not $RE$?
So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages.
I'm wondering, is ...
10
votes
4answers
216 views
Can a runtime environment detect an infinite loop?
Would it be possible for a runtime environment to detect infinite loops and subsequently stop the associated process, or would implementing such logic be equivalent to solving the halting problem?
...
0
votes
0answers
48 views
Show the problem of a machine visiting infinitely many tape cells on some input is undecidable
I am attempting to prove the following problem is undecidable. Given a Turing machine $M$ and input $x$, does $M$ visit infinitely many tape cells on input $x$?
I am considering a reduction from the ...
2
votes
1answer
73 views
Does Turing Machine divergence depend on the input?
If there is a Turing Machine $M_e$ (computing some partially computable function $f$), is there an algorithm to decide if $f$ diverges for all possible inputs?
6
votes
1answer
48 views
Program synthesis, decidability and the halting problem
I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that ...
2
votes
2answers
77 views
Clarification on halting predicate computability
I am tackling the halting problem right now and its remarkable theorem. My book states $\text{HALT}(x,y)$ is true if $\psi^{(1)}_{\mathcal P}$ is defined and conversely $\text{HALT}(x,y)$ is false if ...
2
votes
2answers
95 views
Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?
I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem.
Halting ...
5
votes
1answer
101 views
Showing the function=? is impossible
Here's a lab from a first-year computer science course, taught in Scheme: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf
At the end of the lab, it basically presents the halting ...
3
votes
1answer
77 views
Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?
I have a book that proves the halting problem with this simple statement:
$$
A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon
$$
It states that halting problem reduces to the ...
0
votes
1answer
103 views
Determining the classification of languages
$L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$ halts on $w$}\}$
$L_1 = \{ \langle M, w, 1 \rangle \mid \text{$M$ does not halt on $w$}\}$
$L = L_0 \cup L_1$
I need to determine where ...
3
votes
2answers
248 views
What helpful solution does the Halting Problem give to computing?
What problem does the halting problem solve in computing, whether theoretical or practical?
It is very easy to debug code which loops forever, just signal the debugger to break if the program is ...
14
votes
7answers
408 views
Human computing power: Can humans decide the halting problem on Turing Machines?
We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines ...
1
vote
1answer
98 views
Showing that the set of TMs which visit the starting state twice on the empty input is undecidable
I'm trying to prove that
$L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$.
I'm not sure whether to reduce the halting ...
0
votes
0answers
30 views
Are there programming languages that allow the expression of exactly all terminating algorithms? [duplicate]
Possible Duplicate:
Why are the total functions not enumerable?
Are there programming languages that allow to express every algorithm that terminates but no nonterminating programs?
I ...
10
votes
4answers
436 views
Does a never-halting machine always loop?
A Turing machine that returns to a previously encountered state with its read/write head on the same cell of the exact same tape will be caught in a loop. Such a machine doesn't halt.
Can someone ...
11
votes
6answers
399 views
Algorithm to solve Turing's “Halting problem”
"Alan Turing proved in 1936 that a general algorithm to solve the
halting problem for all possible program-input pairs cannot exist"
Can I find a general algorithm to solve the halting problem ...
