Questions tagged [halting-problem]

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

Filter by
Sorted by
Tagged with
144
votes
12answers
48k views

Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia [article][1] correctly explains that a deterministic ...
27
votes
7answers
6k views

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
59
votes
10answers
10k 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 ...
22
votes
6answers
3k 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 for ...
29
votes
7answers
5k views

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...
7
votes
1answer
3k views

Why can't we solve the Halting Problem by using Artificial Intelligence? [duplicate]

Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a ...
10
votes
1answer
907 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 ...
4
votes
1answer
6k views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
6
votes
1answer
12k views

Halting problem reducing to the blank tape halting problem

I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this. The blank tape problem takes a machine and an empty tape and ...
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 ...
17
votes
4answers
2k views

Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic. Hence my own understanding of the halting problem is primarily for ...
6
votes
2answers
256 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 ...
72
votes
5answers
12k views

Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?

I've always thought vaguely that the answer to the above question was affirmative along the following lines. Gödel's incompleteness theorem and the undecidability of the halting problem both being ...
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 ...
22
votes
2answers
2k views

Are there programs that never halt and have no non-termination proof?

Like black holes in computer science. We can only know they exist but when we have one of them we will never know it's one of them.
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 ...
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 ...
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 ...
13
votes
3answers
5k 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 ...
11
votes
3answers
2k views

Does the proof of undecidability of the Halting Problem cheat by reversing results?

I have trouble understanding Turing's halting problem. His proof assumes that there exists a magical machine $H$ which could determine whether a computer would halt or loop forever for a given input. ...
11
votes
1answer
620 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 ...
7
votes
1answer
3k views

Why is the halting problem semi-decidable?

This is what is know about halting problem and semi-decidability :- Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x. A ...
8
votes
1answer
528 views

Does Church-Turing thesis also apply to artificial intelligence?

By Church-Turing's thesis, it is impossible to design an algorithm to decide the halting problem. Does the word algorithm in this context include artificial intelligence or not, that is, does ...
6
votes
1answer
938 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 ...
6
votes
1answer
2k views

Decidability of halting problem for DPDAs with $\epsilon$-transitions?

For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space. But what about PDAs with $\...
5
votes
1answer
304 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 ...
4
votes
1answer
446 views

If the Halting Problem was solvable, and we solved it, what would be its implications?

Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved. What would be the Halting Problem's implications in ...
4
votes
1answer
1k views

Does the Halting Problem prove that true Artificial Intelligence is impossible?

The Halting Problem demonstrates that there are things that a machine can never be programmed to do. Is this proof that true Artificial Intelligence - that is, the ability for a machine to think and ...
5
votes
1answer
637 views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
1
vote
0answers
99 views

Prove that $H$ reduces to $H\varepsilon$

I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem). I am very confused how to PROVE it, I mean it is clear that we can ...
1
vote
1answer
276 views

Reducing the infinite language problem to halting problem

Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $. It is easy to show with Rices theorem that $INF$ is not decidable. ($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$). How ...
-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 ...
16
votes
5answers
4k views

Turing machine + time dilation = solve the halting problem?

There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer ...
24
votes
4answers
4k views

Is the halting problem decidable for pure programs on an ideal computer?

It's fairly simple to understand why the halting problem is undecidable for impure programs (i.e., ones that have I/O and/or states dependent on the machine-global state); but intuitively, it seems ...
9
votes
2answers
894 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 ...
10
votes
4answers
3k views

Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets. This question is somewhat different. It asks whether ...
8
votes
3answers
941 views

Halting problem - one issue that's bothering me

To my knowledge, halting problem asks if there exists a program that decides whether a program being tested, given some input data (no matter what program it is, or what input data we give) will ...
7
votes
6answers
993 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 ...
5
votes
2answers
703 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 ...
3
votes
1answer
172 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 ...
3
votes
4answers
266 views

If modern computers aren't actually Turing-complete, does that mean that it is possible to determine if a program run on such a computer halts?

The halting problem says that it is impossible to create a general algorithm which can for all inputs and programs determine whether they halt. However, this assumes that the programs and/or the ...
2
votes
2answers
441 views

Is the halting problem decidable by an “infinite Turing machine”?

It has been shown of course that the halting problem is undecidable. That is, we cannot formulate a Turing machine that will decide for any arbitrary turing machine whether it will halt or not. ...
1
vote
2answers
143 views

Is the below language Non R.E?

$L_0=\{\langle M,w,0\rangle\mid M \text{ halts on } w\}$ $L_1=\{⟨M,w,1⟩\mid M \text{ does not halts on } w\}$ Here $\langle M,w,i \rangle$ is a triplet, whose first component $M$ is an encoding of a ...
3
votes
1answer
982 views

Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

I have difficulties to differentiate the $H_0$ from the $E_{TM}$ problem. What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow input~...
2
votes
0answers
68 views

Detecting loops in NPDAs

I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it. I used to think that you could detect an infinite loop by meeting ...
2
votes
3answers
187 views

Misunderstanding Turing's Halting-Problem Argument

I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM_MtS_w4) . I’m having some difficulty understanding the argument as it is made. Let me explain it ...
2
votes
1answer
1k views

What is the complement of Halting Problem?

I understand that Halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. ...
1
vote
1answer
101 views

Does a DPDA halt on all inputs?

Given a deterministic DPA, is it possible to tell whether it halts on all possible inputs? Is this problem decidable? The standard halting problem is "Given a DPDA and an input $x$, determine ...