Hacker News Reader

Comment by Paul-Craft | Hacker News Reader

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-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

View on HN

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.

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

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.

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".

But wouldn't Turning completeness allow you to construct any computations, including the ones that will finish operations in specific limited steps?

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.

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).

This was my thought. It would imply that a Turing-complete machine should be able to solve NP problems in O(1) time.

Ah yea, good point!

Where does it say it's a surprise?

On the contrary, in summary it says: "The search has finally ended ..."

Reply on news.ycombinator.com