# Questions tagged [halting-problem]

Given a program and the input for it, does it halt or run forever?

38 questions
Filter by
Sorted by
Tagged with
1answer
260 views

### Can the halting problem be solved probabilistically? [closed]

Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
1answer
100 views

### Is this a good definition of computability? [closed]

I still haven't found a good definition of computability. All the definitions are either too vague, or they delegate the definition to another loaded term like "anything that uses math to solve a ...
2answers
152 views

### Turing meta-oracle

Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
1answer
251 views

### Uniform mortality problem for Turing Machines

Consider the following generalisation of the mortality problem for Turing Machines. Given a Turing Machine $M$. Is there a bound $k_M$ such that starting from any configuration $c$ machine $M$ ...
1answer
281 views

### What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based ...
0answers
154 views

### Solving the Halting problem for most inputs [closed]

Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing ...
2answers
498 views

### Are all turing machines paths predictable?

I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has ...
1answer
340 views

### “Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes” — Worthy of arXiv.org?

Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you ...
2answers
371 views

### For a specific unbounded Turing machine, is its Halting problem undecidable?

The question is on the title. To make it clearer, I state some facts. We all know that the Halting problem with input is undecidable. It leads to, given a specific input (e.g. empty string), the ...
1answer
1k views

### How good can a halting detector be?

Is there a Turing Machine that can decide whether almost all other Turing Machines halt? Suppose we have some enumeration $\mathbb{N} \rightarrow \{M_i\}$ of Turing machines, and some notion of "...
1answer
285 views

### Practical approaches to solving whether programs will halt

What kinds of systems are available that accept a certain program $P$ and attempts to figure out "the program does terminate" or "the program does not terminate" and output a proof of one or the other?...
2answers
293 views

### Program equivalence wherein the programs are known to always halt

Say I have two programs with possibly infinite state spaces and some oracle has asserted that they both always halt. Can I always decide if they're contextually equivalent? If yes, is there a known ...
2answers
385 views

### Automated proving that a program doesn't halt

If you are a computer and you are given a program $P$ (with no input parameter) that doesn't halt, how would you try proving it doesn't halt ? (here proving means convincing ourselves that it is true)...
2answers
672 views

### Halting problem for finite tape TM [closed]

If we have a primitive CPU/computer with small amount of registers and/or RAM, it is easy to check if the program will loop endlessly: just write down all registers/RAM cells states at each state and ...
1answer
335 views

### Is there a good notion of non-termination and halting proofs in type theory?

Constructive type theory with its basic interpretation under the curry howard correspondence consists only of total, computable functions. In the literature, some has been said on using "computational ...
1answer
429 views

### Constructive proof of the Halting Problem

Does there exist any constructive (indeed, computable) proof of the Halting Problem? All the ones I have encountered make use of proof by contradiction. As an aside, some proofs I have encountered ...
1answer
232 views

### Polynomial-time reductions between undecidable languages

The Turing degree $\mathbf{0}'$ is defined as all languages Turing-equivalent to the halting problem. In fact any recursively enumerable language is polynomial-time reducible to the halting problem. ...
0answers
205 views

### The halting problem in computational models weaker than Turing machines

What are the main results and/or literature on the (self) halting problem for other machines than Turing machines? Alternatively, what would be the right keywords or tags to search for it. I am ...
1answer
152 views

### Undecidable Single Programs [closed]

So the halting problem basically states that there cannot exist any finite length algorithm for automatically verifying if other finite length algorithms terminate. But suppose I start listing out ...
0answers
69 views

### Is there value in a faster soultion for the Halting Problem in a Linear Bounded Automata?

Sorry for being so informal, but I was thinking a bit about how the Halting Problem is solvable on a LBA but very very slow, in that if you have gone though more states in execution then the total ...
1answer
270 views

### Are All Turing-Uncomputable Sets Isomorphic to the Halting Problem? [closed]

We know from computability theory that some sets are recursively computable on a Turing machine and others not. Many such sets or languages that cannot be recognized by a Turing machine seem to have ...
2answers
937 views

### Turing machines whose termination is unprovable?

I have a naive question: does there exist a Turing machine whose termination is true but unprovable by any natural, consistent and finitely axiomatizable theory? I ask for a mere existence proof ...
4answers
5k views

### What is the smallest Turing machine where it is unknown if it halts or not?

I know that the halting problem is undecidable in general but there are some Turing machines that obviously halt and some that obviously don't. Out of all possible turing machines what is the smallest ...
1answer
130 views

### Is refuting candidate deciders of the halting problem computable? [closed]

No Turing machine can decide whether any given Turing machine will halt for a given input. That is: If you give me a Turing machine which you claim can take a Turing machine and an input for that ...
1answer
623 views

### Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem?

Since both proofs make use of the diagonal argument, I’m wondering whether there is an obscure link between the existence of uncountable infinite sets and the undecidability of the halting problem. ...
1answer
184 views

### Explanation of 1-generic to prove undecidability of halting problem

This question is about an answer in question Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ? Bjørn Kjos-Hanssen answer ...
2answers
2k views

### Complexity of the halting problem

One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind: \$...
2answers
4k views

### What is the “nearest” problem to the Collatz conjecture that has been successfully resolved?

I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ...
1answer
2k views

### Halting problem, uncomputable sets: common mathematical proof?

It is known that with a countable set of algorithms (characterised by a Gödel number), we cannot compute (build a binary algorithm which checks belonging) all subsets of N. A proof could be ...
0answers
186 views

### Can every undecidability proof be converted into diagonalization proof? [duplicate]

Possible Duplicate: Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ? As is stated, can every undecidability proof can ...
1answer
762 views

### Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ...
2answers
657 views

### Is halting that hard? [Yes] [closed]

I want to make a modification to the halting problem. The output now has two possibilities: This program halts and it does not have the crossing structure (defined below); This program does not halt ...
2answers
3k views

### Can chess simulate a Universal Turing Machine?

I am looking to get a definite answer to title question. Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white ...
2answers
910 views

### Collatz Conjecture & Grammars / Automata

I was wondering if there is a good bibliography of attempts to investigate the Collatz conjecture as a formal grammar? (or any other attempts in the CS community to deal with this class of generative ...
2answers
263 views

### formalizing a statement about the expressive power of programming languages wrt divergence

In the Coq'Art book the authors mention in passing that any language that can calculate all computable functions must also be able to express diverging computations. Or in other words, there can be no ...
1answer
672 views

### Undecidable problems not Turing-complete?

are there systems whose nontrivial properties can't be decided by Turing machines, but for which a Turing machine with an oracle able to find out these properties isn't able to solve the Halting ...
3answers
2k views

### Is there a sensible notion of an approximation algorithm for an undecidable problem?

Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them. For example, the halting problem is undecidable, but practical progress can be ...
1answer
1k views

### Alternative Turing Machine Proofs

I am asking this question again. I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me. I am looking for a TM Halting Problem proof that ...