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

learn more… | top users | synonyms

0
votes
1answer
34 views

Turing machines and languages — recursive (enumerable) or not

For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could ...
4
votes
2answers
165 views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
1
vote
1answer
52 views

Regarding Turing Machine Halting Problem [closed]

All problems solved by standard today's general purpose computer can be solved by standard Turing machine.As general purpose computer can't do more than Turing machine so The Turing machine halting ...
5
votes
1answer
69 views

Possible to construct a probabilistic halting problem solver?

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions. So I was thinking, much in the way that some ...
2
votes
2answers
105 views

Why is the halting problem unsolvable by a turing machine? [duplicate]

So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable. So any human can determine if a problem halts with rigorous inspection, so why can't a ...
1
vote
1answer
84 views

Trying to break the proof of undecidability of the halting problem

Posted this question on cstheory.SE where they said to go here: I read the demonstration of the Halting problem, it is done by reductio ad absurdum where the push to get to the absurd is to use ...
1
vote
0answers
80 views

What if the proof for the halting problem was wrong? [closed]

What would the repercussions on computer science theory as we know it today be if the proof for the incomputability of the halting problem was shown to be wrong? What would change in terms of the ...
3
votes
1answer
88 views

Is the halting problem specific to Turing machines?

The proofs that the halting problem is undecidable seem to make very few assumptions about the kind of program/machine under consideration: just that the programs take one input and either loop or ...
2
votes
2answers
59 views

How to prove that “Total” is not recursive (decidable)

$\mathrm{Halt} = \{ (f,x) | f(x)\downarrow \}$ is r.e. (semi-decidable) but undecidable. $\mathrm{Total} = \{ f | \forall x f(x)\downarrow \}$ is not r.e. (not even semi-decidable). I need some help ...
7
votes
3answers
182 views

Is there a TM that halts on all inputs but that property is not provable?

Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason? I am wondering if this question has been studied. Note, "unprovable" could mean a ...
3
votes
2answers
111 views

Can a method be written if the language is undecidable?

If a language is decidable, we can write a method that always halts and returns true for each string that is an element of the language and ...
1
vote
1answer
50 views

Confusing equivalence $\Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$

Let $B$ be a recursive enumerable set and $B = W_n$, where $W_n = \{x \in \mathbb N \mid \Phi(x,n)\downarrow\}$ and $\Phi^{(n)}(x_1, \ldots, x_n, y)$ is the value of the function at the terminal ...
2
votes
2answers
100 views

Alternative proof for the undecidability of $A_{TM}$

The proof of the undecidability of $A_{TM}$ in Michael Sipser's textbook* contains the definition of a Turing Machine, which accepts the encoding of a TM, if this ...
0
votes
2answers
139 views

Is oracle computer capable of doing infinite loops?

Solve this problem: "build an infinite binary oscilator" With a Turing Machine we can solve it a=False While True: a=not a print a, then output will be ...
1
vote
1answer
88 views

Can a Turing machine decide if a LOOP program stops for the integer input 0

This is a question I found in a practice exam while I am preparing for my mid term exam. The answer needs justification, either a pseudo code or a logical explanation why not. What puzzled me about ...
1
vote
1answer
397 views

Relationship between Undecidable Problems and Recursively Enumerable languages

I have read the Wikipedia article on Recursively Enumerable languages. The article suggests that the halting problem is recursively enumerable but undecidable. My idea till today was that the halting ...
3
votes
1answer
73 views

Halting problem

I have some concerns about the Halting problem. This is the proof I know: Let $h(M, i)$ be a function, $M$ being Turing machine and $i$ input for the Turing machine. Let $h(M, i)$ output true ...
3
votes
1answer
58 views

Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts?

BB(n) is roughly the maximum number of new states an n-state TM can run into without halting. So for a particular n, if we know BB(n), then we can find out if an arbitrary n-state TM halts by running ...
1
vote
1answer
108 views

Undecidability of whether a given TM halts or only has loops which can be detected by some TM

This might be a bit of an abstruse question, but it's something I've been trying to prove. I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all ...
-1
votes
1answer
125 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 ...
5
votes
2answers
115 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
800 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? ...
1
vote
2answers
106 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
109 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?
8
votes
1answer
133 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
96 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
126 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 ...
6
votes
1answer
115 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
88 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
121 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
315 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 ...
21
votes
7answers
1k 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
132 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
31 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 ...
11
votes
4answers
525 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
639 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 ...