Tagged Questions

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

learn more… | top users | synonyms

2
votes
0answers
38 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
77 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 ...
8
votes
2answers
715 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 ...
23
votes
4answers
3k 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
73 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 ...
6
votes
1answer
287 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
147 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 ...
6
votes
2answers
634 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: ...
9
votes
1answer
1k 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"). ...
20
votes
1answer
1k 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 ...
4
votes
0answers
165 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 ...
-2
votes
1answer
570 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
506 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 ...
13
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 ...
15
votes
2answers
662 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
235 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
470 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 ...
36
votes
2answers
828 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
658 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 ...