Questions tagged [halting-problem]

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

7
votes
6answers
985 views

How is Turing's Solution to the Halting Problem Not Simply “Failure By Design”?

I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer. Here is my understanding of the Halting Problem: Let $M$ be the set of all ...
3
votes
1answer
143 views

Smallest non-halting unlambda program

Is ```sii``sii the smallest Unlambda program that doesn't halt? In other words, what is the smallest non-terminating combinator term in SKI augmented with $C$ (...
9
votes
2answers
884 views

Halting problem without self-reference

In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a ...
3
votes
1answer
96 views

Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?

Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that ...
3
votes
3answers
990 views

If Halting problem is decidable, are all RE languages decidable? [closed]

Assume the halting problem was decidable. Is then every recursively enumerable languagerecursive?
3
votes
1answer
171 views

The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages

Can the following two statistics be bounded: the proportion of halting programs vs non-halting programs the proportion of decidable vs undecidable languages For example, can we say that one class is ...
1
vote
1answer
424 views

Examples for incomparable semi-decidable but undecidable languages

In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made: 'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, ...
0
votes
1answer
453 views

Why is $A_{TM}$ reducible to $HALT_{TM}$?

In Sipser, there is a proof I don't understand. First he established the undecidability of $A_\mathrm{TM}$, the problem of determining whether a Turing machine accepts a given input. $$A_\mathrm{...
6
votes
3answers
3k views

Are all undecidable/uncomputable problems reducible to the Halting problem? [duplicate]

Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an ...
10
votes
1answer
902 views

Are there any existing problems that wouldn't be solvable with a halting oracle?

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
8
votes
3answers
1k views

Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it?

When I first heard of these things I was very fascinated as I thought it sets really a limit to mathematics and science in general. But how practically relevant are these things? For the Halting ...
30
votes
7answers
2k views

Is there a connection between the halting problem and thermodynamic entropy?

Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem. A TM is an abstract concept of a machine (or engine if ...
4
votes
3answers
171 views

Undecidability instance on a “find a proof/disproof” machine

I'm following through the proof of the impossibility of the Halting problem for the umpteenth time. It all makes sense logically, but not intuitively. A question I got stuck on: Suppose we built the ...
10
votes
1answer
416 views

Hilbert's 10th Problem and Chaitin's Diophantine Equation “Computer”?

In Chaitin's Meta Math! The Quest For Omega, he briefly talks about Hilbert's 10th Problem. He then says that any Diophantine Equation $p=0$ can be changed into two equal polynomials with positive ...
5
votes
1answer
130 views

Is there a largest class of halting programs?

The halting problem says that a Turing machine cannot decide if another Turing machine halts. However, we know that it is possible to determine if some programs halt. For example, FORTRAN DO ...
0
votes
1answer
123 views

How can a problem be undecidable yet enumerable? [duplicate]

How can something be enumerable but be un-decidable ie, this states the halting set is un-decidable and enumerable. Enumerable means it can be computed, ie has the same cardinality as natural numbers ...
0
votes
0answers
154 views

Does the head of TM M ever move into cell x when processing Input I?

The question is whether this is recursive or not. I first thought that it wasn't but then I read this question which seems similar and is recursive. Is it decidable whether a TM reaches some position ...
0
votes
1answer
737 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 ...
13
votes
3answers
4k 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 ...
0
votes
1answer
141 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
299 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
4k 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 ...
2
votes
1answer
373 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 ...
6
votes
1answer
932 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
772 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 ...
16
votes
3answers
688 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
135 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
151 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 ...
3
votes
2answers
154 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 ...
1
vote
2answers
404 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
280 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 ...
6
votes
1answer
5k 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 ...
6
votes
1answer
331 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
98 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 ...
2
votes
1answer
301 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
1k 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 ...
6
votes
2answers
253 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 ...
18
votes
4answers
7k 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? ...
2
votes
2answers
421 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 ...
3
votes
1answer
486 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?
11
votes
1answer
619 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 ...
3
votes
2answers
156 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 $...
5
votes
2answers
351 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
209 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 problem,...
3
votes
1answer
172 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 ...
1
vote
1answer
209 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 in ...
5
votes
2answers
700 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 ...
58
votes
10answers
9k 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 ...
2
votes
1answer
667 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 ...
21
votes
4answers
3k 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 ...