Skip to main content

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
182 votes
13 answers
67k 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 correctly explains that a deterministic machine ...
Brent's user avatar
  • 2,553
93 votes
6 answers
18k 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 ...
Marc van Leeuwen's user avatar
65 votes
11 answers
14k 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 ...
bitmask's user avatar
  • 1,755
36 votes
8 answers
11k 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. ...
MaiaVictor's user avatar
  • 4,137
33 votes
7 answers
7k 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 ...
user118967's user avatar
32 votes
7 answers
3k 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 ...
Nikos M.'s user avatar
  • 979
26 votes
4 answers
5k 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 ...
Jules's user avatar
  • 632
26 votes
6 answers
4k 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 ...
user avatar
24 votes
2 answers
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.
Otakar Molnár López's user avatar
22 votes
4 answers
5k 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 ...
hollow7's user avatar
  • 527
22 votes
5 answers
5k views

Could the Halting Problem be "resolved" by escaping to a higher-level description of computation?

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox. So I got to wonder: ...
H2CO3's user avatar
  • 323
22 votes
3 answers
5k views

Can a program exist that halts only if it can prove that it doesn't halt?

Consider a program P that enumerates possible proofs in some proof system and halts only if it finds a valid proof that P does not halt. Clearly no such proof exists, or the program would eventually ...
Silver's user avatar
  • 417
22 votes
6 answers
3k views

Halting problem theory vs. practice

It is often asserted that the halting problem is undecidable. And proving it is indeed trivial. But that only applies to an arbitrary program. Has there been any study regarding classes of programs ...
Jack Fleming's user avatar
22 votes
1 answer
2k views

Is possible to prove undecidability of the halting problem in Coq?

I was watching the "Five Stages of Accepting Constructive Mathematics" by Andrej Bauer and he says that there is two kinds of proof by contradiction (or two things that mathematicians call proof by ...
Rafael Castro's user avatar
20 votes
6 answers
5k views

Is halting problem computable for particular inputs/assumptions

From my understanding of the proof that halting problem is not computable, this problem is not computable because if we have a program P(x) which computes if the program x halts or not, we got a ...
ela's user avatar
  • 315
20 votes
4 answers
3k 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 ...
babou's user avatar
  • 19.5k
19 votes
3 answers
7k 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 ...
user5507's user avatar
  • 2,191
19 votes
6 answers
10k 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? ...
Kyle Strand's user avatar
18 votes
5 answers
5k 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 ...
K--'s user avatar
  • 283
18 votes
4 answers
1k 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 "...
vzn's user avatar
  • 11k
14 votes
5 answers
4k views

How to prove the existence of a number which cannot be written by any algorithm?

I have the problem: Show that there exists a real number for which no program exists that runs infinitely long and writes that number's decimal digits. I suppose it can be solved by reducing ...
fresheed's user avatar
  • 143
14 votes
5 answers
5k views

Is it provably true/false that for a program, there exists a proof whether it halts or not?

A standalone statement of my question Given a program that takes no argument, we are interested in whether the program will eventually terminate. My question is this: Theoretically speaking, can we ...
DatoClement's user avatar
14 votes
1 answer
949 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 ...
Patrick87's user avatar
  • 12.9k
13 votes
2 answers
2k 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 ...
ike's user avatar
  • 235
13 votes
2 answers
2k 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 ...
zpavlinovic's user avatar
  • 1,654
12 votes
3 answers
3k 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. ...
user27819's user avatar
  • 131
12 votes
3 answers
1k views

Chaitin's constant is normal?

According to this source, Chaitin's constant $\Omega$ is normal. Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm ...
Anon21's user avatar
  • 345
11 votes
3 answers
3k views

Detecting if three Turing Machines halt given a magic oracle that is only used twice

We were given a question in class as follows: You have a "magic oracle" that can decide if a Turing Machine halts. You have three TMs $T_1, T_2, T_3$. Device an algorithm that decides which ...
lombardo2's user avatar
  • 121
10 votes
4 answers
4k 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 ...
yters's user avatar
  • 1,427
10 votes
2 answers
2k views

Is it possible that the halting problem is solvable for all input except the machine's code?

This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help. Is it possible that the halting problem is decidable for any TM on any ...
CS101's user avatar
  • 103
10 votes
1 answer
8k views

Why is the halting problem semi-decidable?

This is what is known about the halting problem and semi-decidability :- The 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. ...
Zephyr's user avatar
  • 993
10 votes
1 answer
591 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 ...
Steady's user avatar
  • 103
10 votes
2 answers
4k 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 $\...
lukas.coenig's user avatar
10 votes
1 answer
538 views

Is the halting problem decidable for 3 symbol one dimensional cellular automata?

I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata. Definition Let $f(w,i)$ denote the configuration of the system at time step $i$. ...
Pavel's user avatar
  • 1
9 votes
1 answer
5k 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 ...
nmomn's user avatar
  • 377
9 votes
3 answers
7k 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 ...
user13675's user avatar
  • 1,624
9 votes
3 answers
1k 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 ...
user4205580's user avatar
9 votes
1 answer
23k 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 ...
revisingcomplexity's user avatar
8 votes
6 answers
1k 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 ...
StudentsTea's user avatar
8 votes
2 answers
1k views

Halting Problem without self-reference: why does this argument not suffice (or does it)?

I'm trying to find a way to explain the idea of the Halting Problem proof in as accessible a manner as possible (to undergrad CS students). The simplest argument I have found is this one; this is ...
badroit's user avatar
  • 727
8 votes
3 answers
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 ...
Nocta's user avatar
  • 121
8 votes
1 answer
2k views

What is the complexity of theorem proving?

I'm learning some computer science and mathematics by myself. I know that proving theorems in ZFC is undecidable in general, but, is there a formal way to express how complex it is? Is it as complex ...
Otakar Molnár López's user avatar
8 votes
3 answers
1k views

Undecidability of telling if a program returns true or false

Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are ...
Mario Carneiro's user avatar
8 votes
1 answer
1k 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 ...
jameshfisher's user avatar
8 votes
1 answer
3k 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 today'...
Zaenille's user avatar
  • 191
7 votes
3 answers
2k views

The 'directionality' of reductions?

I've been finding myself a bit confused with the direction of reductions used to show that certain languages are not recursive. For example, let us say we want to determine if the Halting Problem ($...
Chris T's user avatar
  • 205
7 votes
1 answer
988 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 ...
M a m a D's user avatar
  • 1,529
7 votes
2 answers
386 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 ...
Joey Eremondi's user avatar
7 votes
1 answer
16k 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 ...
marcove3's user avatar
7 votes
1 answer
1k views

Machine Learning to predict the Halting Problem

I seem to recall an academic paper from some years ago which used machine learning (possibly genetic or evolutionary programming) to predict whether a Turing Machine would halt. By predict, I mean ...
NietzscheanAI's user avatar

1
2 3 4 5
9