Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [halting-problem]

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

1
vote
0answers
87 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 ...
7
votes
2answers
305 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 ...
7
votes
1answer
315 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 ...
1
vote
2answers
123 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 ...
11
votes
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 "...
1
vote
1answer
163 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?...
6
votes
2answers
159 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 ...
3
votes
2answers
355 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)...
0
votes
2answers
494 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 ...
9
votes
1answer
254 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 ...
-1
votes
1answer
294 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 ...
2
votes
1answer
179 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. ...
10
votes
0answers
189 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 ...
-2
votes
1answer
141 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 ...
2
votes
0answers
67 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 ...
-4
votes
1answer
215 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 ...
9
votes
2answers
886 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 ...
31
votes
4answers
4k 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 ...
0
votes
1answer
109 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 ...
8
votes
1answer
475 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. ...
4
votes
1answer
175 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 ...
6
votes
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: $...
14
votes
2answers
3k 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 ripe for such problems"). ...
29
votes
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 ...
5
votes
0answers
183 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 ...
-2
votes
1answer
715 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 ...
-4
votes
2answers
632 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 ...
15
votes
2answers
2k 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 ...
16
votes
2answers
802 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 ...
2
votes
2answers
258 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 ...
2
votes
1answer
639 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 ...
48
votes
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 ...
-5
votes
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 ...