Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with halting-problem
Search options answers only
not deleted
user 3247
Given a program and the input for it, does it halt or run forever?
46
votes
Accepted
What is the smallest Turing machine where it is unknown if it halts or not?
The largest Turing machines for which the halting problem is decidable are:
$TM(2,3), TM(2,2), TM(3,2)$ (where $TM(k,l)$ is the set of Turing machines with $k$ states and $l$ symbols).
The decidabi …
- 23.2k
4
votes
Accepted
Are all turing machines paths predictable?
This is another way to prove that not all Turing machines are predictable.
First it's easy to note that:
all halting machines are predictable;
all machines that loop forever on a finite portion of …
- 23.2k
4
votes
Complexity of the halting problem
Just an extended comment: I'm not an expert, but for what regards 1., something can be said if you interpret: $HALT(k) = 1$ iif $TM_k$ halts on the empty tape.
In this case the string $s$ that lists …
- 23.2k
4
votes
Can chess simulate a Universal Turing Machine?
Yesterday I googled around to check the status of this problem and I found this new (2012) result:
Dan Brumleve, Joel David Hamkins and Philipp Schlicht, The mate-in-n problem of infinite chess is de …
- 23.2k
6
votes
Accepted
Uniform mortality problem for Turing Machines
The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966))
The uniform mortality problem undecidability follows from the following:
Theor …
- 23.2k
2
votes
Halting problem proofs that do not utilise self-reference or diagonalization
P1 Perhaps you can somewhat avoid self reference in this way.
Let $S_k$ be the total number of steps performed by the halting Turing machines of size $\leq k$ in their computation.
Suppose the Halting …
- 23.2k
27
votes
Accepted
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
An extended comment:
Collatz-like sequences can be computed by small Turing machines having few symbols and states. In "Small Turing machines and generalized busy beaver competition" by P. Michel (20 …
- 23.2k