Today in a talk with a friend of mine I had an idea of extending cellular automatons to transfinite working time. I know it has already been considered, but, as far as I can tell, GoL extended to infinite numbers of steps hasn't been considered. At limit stages one would take limsup of value of the cell at earlier times. One can try to compare it to Hamkins-Kidder ITTMs: notions of writable reals and clockable ordinals could be extended fairly easily (e.g. configurations and stabilization times reachable from finite initial seed). What I am interested in is computational power of these machines. It is really unclear how one might simulate an ITTM in such system, because we can't guarantee if some operation will not repeat infinitely many times, and that can really mess up our system (for example, simple blinker becomes unstable, and it doesn't stabilize until stage $\omega5+25$).

My question is: has infinite time GoL ever been considered, and if so, has it been proven that it is ITTM-computably universal?

  • 1
    $\begingroup$ Great question! It seems to me that the usual encodings of Turing machines will not survive the limit process, and so to get ITTM power here one will need far more robust encodings of Turing machines into GoL. $\endgroup$ – Joel David Hamkins May 22 '14 at 23:12
  • $\begingroup$ Yes, standard Turing machine built in GoL will break at limit stages. Even if we somehow could make it work for more than $\omega$ steps, I suspect it's impossible to extend it past $\omega^2$ for this reason: if we could somehow simulate ITTM, we have to somehow know that it's limit stage. So there'd have to be some "check if it's limit" circuit, which would be active infinitely many times before $\omega^2$, which would probably break it. $\endgroup$ – Wojowu May 23 '14 at 10:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.