Timeline for Does this Foo machine halt?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10, 2019 at 12:34 | comment | added | Arnauld | Just an empirical result, but brute-forcing the longest cycle among halting machines on a tape of length \$n\$ suggests that a tighter upper bound is \$\lfloor2^n.log(n)/n\rceil\$. | |
| Aug 10, 2019 at 10:05 | history | edited | Jo King | CC BY-SA 4.0 | added explanation |
| Aug 9, 2019 at 17:54 | comment | added | user41805 | Sketch of a proof for a Foo machine with tape a_1 ... a_n 0 . Consider an n-cube of the signs of each cell with directed edges (= an iteration of Foo) between vertices (= states), visiting the same vertex via any loop of edges will result in the IP being in the same position it started with. Proof: In a loop, the IP travels in each dimension an even number of times, ie the IP changes by k×(a_j + (-a_j)) % n ≡ 0 for each dimension, hence it always returns to the same position, only ever seeing 1 state out of n states for each vertex, ie a total max of 2^n states (= number of vertices of cube). | |
| Aug 9, 2019 at 15:30 | history | edited | Jo King | CC BY-SA 4.0 | -7 bytes |
| Aug 9, 2019 at 15:29 | comment | added | Magma | The state of the Foo machine also includes the location of the pointer, not just the signs of each cell. | |
| Aug 9, 2019 at 6:26 | history | edited | Jo King | CC BY-SA 4.0 | -3 bytes |
| Aug 9, 2019 at 5:54 | history | edited | Jo King | CC BY-SA 4.0 | -2 bytes + explanation |
| Aug 9, 2019 at 5:48 | history | answered | Jo King | CC BY-SA 4.0 |