Given a program and the input for it, does it halt or run forever?
-3
votes
0answers
56 views
Halting problem? [closed]
I have some concerns about the Halting problem. This is the proof I know:
Let $h(M, i)$ be a function, $M$ being Turing machine and $i$ input for the Turing machine. Let $h(M, i)$ output true ...
-1
votes
0answers
62 views
Undecidability of whether a given TM has only mechanically detectable loops or always halts [migrated]
This might be a bit of an abstruse question, but it's something I've been trying to prove.
I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all ...
0
votes
0answers
67 views
loop invariants in proving program termination
consider two similar pieces of (pseudo)code:
A:
n = f(x)
for (i = 1 to n) do
begin
....
end
B:
x = 1
while (x != 0) do
begin
x = g(x)
....
end
in case A if ...
4
votes
1answer
123 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
470 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:
...
6
votes
1answer
508 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"). ...
13
votes
1answer
623 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
158 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 ...
0
votes
0answers
271 views
Halting problem and Microsoft Visual Studio [closed]
One of the famous problems that one can theoretically can be proven to be unsolvable is the halting problem. Which is an algorithm that can determine other algorithms are going to end at some point or ...
-2
votes
1answer
429 views
Is there any proof that a network made of Turing machines can't solve the halting problem?
My question point to the fact that Turing machines are isolated by definition, but what if they can send, and receive information from/to to other Turing machines, what if they can be "interrupted" at ...
-4
votes
2answers
385 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 ...
12
votes
1answer
1k 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 ...
13
votes
2answers
430 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
212 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 ...
1
vote
1answer
418 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 ...
34
votes
3answers
672 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 ...
-4
votes
1answer
520 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 ...
