Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  Joel David Hamkins May 22 at 23:12
    
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. –  Wojowu May 23 at 10:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.