3 ms·

I'm wondering why this is a surprise, given GoL has been known to be Turing complete for some time, and why one couldn't just bootstrap oscillators of all perio

I'm wondering why this is a surprise, given GoL has been known to be Turing complete for some time, and why one couldn't just bootstrap oscillators of all periods off of some kind of Turing machine construction. https://hackaday.com/2020/11/21/a-computer-in-the-game-of-life/ https://hackaday.com/2020/11/21/a-computer-in-the-game-of-li... Incidentally, the computer in the previous link reminds me a lot of something I've seen implemented in my favorite CA, Wireworld: https://en.wikipedia.org/wiki/Wireworld https://en.wikipedia.org/wiki/Wireworld

armchairhacker 3y ago
I believe Turing completeness means you can simulate all periods divisible by some number(s) n, but the individual steps in the Turing machine construction would take multiple real steps.
GolDDranks 3y ago
Note that each single "step" of the Turing Machine may take n steps of advancing the GoL cellular automaton itself. This means that only periods of n*i where i is an integer corresponding to the number of steps made by the TM, are guaranteed to exist. Worse even, I don't think that a proof of Turing completeness requires there to be any time bounds on the machine, so n might not even be a constant... If that's the case, then Turing completeness only proves that there exists an infinite number of periods of various lengths, but nothing about how comprehensively they "cover" all possible periods.
- kuhewa 3y ago
  In other words, Turing completeness is enough to simulate GoL within GoL, but says nothing about the existence of the p41 oscillator
mmis1000 3y ago
Turning complete does not mean it can finish all operations in specific limited time/step. It only means it can finish the computable calculations "eventually".
- NL807 3y ago
  But wouldn't Turning completeness allow you to construct any computations, including the ones that will finish operations in specific limited steps?
  - kuhewa 3y ago
    So if you know how to construct the missing oscillator, great, you can simulate it in GoL run on your GoL-TM (just slower than if you do it on hardware). That doesn't help discovering the unknown oscillator. As an aside, years into the use of computers to search for oscillators, humans were still beating machines to the punch in discovery of some of the unknown period oscillators, as the paper details.
  - mmis1000 3y ago
    No, your computer is Turning completeness. But it does not mean it will be able to encode a giant AV1 video in a night without dedicated hardware. Although it will do it eventually (probably a week or so).
    - everforward 3y ago
      This was my thought. It would imply that a Turing-complete machine should be able to solve NP problems in O(1) time.
      - NL807 3y ago
        Ah yea, good point!
ranting-moth 3y ago
Where does it say it's a surprise? On the contrary, in summary it says: "The search has finally ended ..."

armchairhacker 3y ago

I believe Turing completeness means you can simulate all periods divisible by some number(s) n, but the individual steps in the Turing machine construction would take multiple real steps.

GolDDranks 3y ago

Note that each single "step" of the Turing Machine may take n steps of advancing the GoL cellular automaton itself. This means that only periods of n*i where i is an integer corresponding to the number of steps made by the TM, are guaranteed to exist. Worse even, I don't think that a proof of Turing completeness requires there to be any time bounds on the machine, so n might not even be a constant... If that's the case, then Turing completeness only proves that there exists an infinite number of periods of various lengths, but nothing about how comprehensively they "cover" all possible periods.

kuhewa 3y ago
In other words, Turing completeness is enough to simulate GoL within GoL, but says nothing about the existence of the p41 oscillator

mmis1000 3y ago

Turning complete does not mean it can finish all operations in specific limited time/step. It only means it can finish the computable calculations "eventually".

NL807 3y ago
But wouldn't Turning completeness allow you to construct any computations, including the ones that will finish operations in specific limited steps?
- kuhewa 3y ago
  So if you know how to construct the missing oscillator, great, you can simulate it in GoL run on your GoL-TM (just slower than if you do it on hardware). That doesn't help discovering the unknown oscillator. As an aside, years into the use of computers to search for oscillators, humans were still beating machines to the punch in discovery of some of the unknown period oscillators, as the paper details.
- mmis1000 3y ago
  No, your computer is Turning completeness. But it does not mean it will be able to encode a giant AV1 video in a night without dedicated hardware. Although it will do it eventually (probably a week or so).
  - everforward 3y ago
    This was my thought. It would imply that a Turing-complete machine should be able to solve NP problems in O(1) time.
    - NL807 3y ago
      Ah yea, good point!

ranting-moth 3y ago

Where does it say it's a surprise? On the contrary, in summary it says: "The search has finally ended ..."