Timeline for Can We Decide Whether Small Computer Programs Halt?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 30, 2013 at 22:30 | comment | added | Benjamin | Depending on the size of $SHIFT(6,3)$ or the existence of smaller Collatz map simulating machines this may or may not actually ever prove to be a tractable way to solve the conjecture. | |
| Dec 30, 2013 at 22:23 | comment | added | Benjamin | I think what I'm saying is basically what is being said here: en.wikipedia.org/wiki/Busy_beaver#Applications All I meant my restricted halting problem was the to determine the halting of the TM in question initial conditions that encode integers. | |
| Dec 30, 2013 at 21:54 | comment | added | Joel David Hamkins | @Benjamin, could you explain your remarks? I don't know what it means to say "the restricted halting problem..is equivalent to the Collatz conjecture", since the former is a finite set and the latter is a true/false assertion. How can knowing the specific numerical value for Shift(6,3) tell us whether every $n$ leads to a terminating sequence? | |
| Dec 30, 2013 at 21:28 | comment | added | Benjamin | There is a 6 state, 3 colour TM (deterministic) for which the restricted Halting problem (only to valid initial states that represent integers in a specific encoding, the obvious 3 colour one) is equivalent to the Collatz conjecture. Thus knowing $SHIFT(6,3)$ would settle the conjecture. However, this number is unknown as is it's status with regard to it's computability. It is also guaranteed to be enormous as it must be bounded below by $SHIFT(6,2)$ which is know to be $> 7.4* ×10^{36534}$. | |
| Dec 30, 2013 at 18:20 | comment | added | The Masked Avenger | I don't think ofthe Collatz conjecture as a "complete" problem in any sense: solving Collatz does not give us much about compleity of many programs. If I have a program run Collatz on all numbers less than 2 tetrated n, then I have a small program which I would like to knowi if it halts. Even if I only get to run it for n less than 7, knowing whether that halts would tell usmore than we currently know about the Collatz sequence. | |
| Dec 30, 2013 at 16:12 | comment | added | Joel David Hamkins | If the Collatz conjecture is true, how could you come to know this from knowing whether a particular small program halts or not? | |
| Dec 30, 2013 at 16:09 | comment | added | Douglas Zare | I wouldn't be surprised if $n$ were smaller than $128$. However, it's not clear to me how to encode the Collatz conjecture as whether a program halts. | |
| Dec 30, 2013 at 2:54 | comment | added | The Masked Avenger | Using macros, obfuscation, and guessing. Even if I am wrong, I would be surprised if the length of n were much larger than 9 (meaning n is larger than 511). | |
| Dec 30, 2013 at 2:20 | comment | added | Bjørn Kjos-Hanssen | 7, how do you get such a small value? | |
| Dec 29, 2013 at 21:07 | comment | added | The Masked Avenger | In particular, I expect length of n is at most 7, so n is less than 128. | |
| Dec 29, 2013 at 21:05 | history | answered | The Masked Avenger | CC BY-SA 3.0 |