Tagged Questions

Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.

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 ...
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 ...
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 ...
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? ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8943058848381042, "perplexity_flag": "middle"}