CA can emulate the behavior of a Turing machine but isn't one itself. To confuse matters, a Turing machine was recently constructed in Game of Life. See: http://www.cs.ualberta.ca/~bulitko/F02/papers/tm_words.pdf .
Game of life has always been known to have equivalent computational power to a Turing machine. However, this was considered only theoretically possible until this guy cooked this up. The organization is wild - check out the link.
The Turing Machine is a computer, analogous to our desktop models. The Rule Set is its programming, the operating mechanism its processor and its tape the display. The same can be said for Cellular Automata, it too is a computer. The Rule Set is its programming, the operating mechanism its processor and its grid the display.
The tape of the TM is a linear display. The grid of the CA is a stack of linear display outputs forming a 2-dimensional grid. They are merely displays.
Both utilize a processor/display combination (mechanical system) driven by their software (the rule set). Viewed in this way, the mechanical part of the computer is simply a device to interpret and display; it does not have its own attributes. Only the program (rule set) has attributes.
We can conclude from this that the essence of the TM is its program; the same can be said for the CA. Although their processors require different software architectures, as do a PC and Mac, the concept of the software is the same.
Therefore, the real essence of both the TM and CA is its rule set and they are conceptually the same. One is an old punch card machine which spits out tickertape; the other a 5” floppy outputting to a matrix printer.
Perhaps the question of sameness resides in whether either or both can be generative: can they re-write their own code.
The TM operates as an nth degree system through its states. But this does not make it generative unless it provides a facility for self-change of the algorithm.
Although the manner of rule set expression in the CA initially appears to be single degree, it is probably an nth degree system with each rule set box analogous to a state. Neither single nor nth degree implies the generative ability of self-change.
If both the TM and CA operate as nth degree systems, no functional dissimilarity is implied. If one is nth degree and the other single degree, that alone does not make their broad conceptual function dissimilar.
If their conceptual definitions permit one and not the other to re-write its code while operating, then they are not equivalent.
If neither or both can re-write code, they are equivalent.
3 comments:
CA can emulate the behavior of a Turing machine but isn't one itself. To confuse matters, a Turing machine was recently constructed in Game of Life. See: http://www.cs.ualberta.ca/~bulitko/F02/papers/tm_words.pdf .
Game of life has always been known to have equivalent computational power to a Turing machine. However, this was considered only theoretically possible until this guy cooked this up. The organization is wild - check out the link.
Clarification on CA = TM:
The Turing Machine is a computer, analogous to our desktop models. The Rule Set is its programming, the operating mechanism its processor and its tape the display.
The same can be said for Cellular Automata, it too is a computer. The Rule Set is its programming, the operating mechanism its processor and its grid the display.
The tape of the TM is a linear display. The grid of the CA is a stack of linear display outputs forming a 2-dimensional grid. They are merely displays.
Both utilize a processor/display combination (mechanical system) driven by their software (the rule set). Viewed in this way, the mechanical part of the computer is simply a device to interpret and display; it does not have its own attributes. Only the program (rule set) has attributes.
We can conclude from this that the essence of the TM is its program; the same can be said for the CA. Although their processors require different software architectures, as do a PC and Mac, the concept of the software is the same.
Therefore, the real essence of both the TM and CA is its rule set and they are conceptually the same. One is an old punch card machine which spits out tickertape; the other a 5” floppy outputting to a matrix printer.
THOUGHTS ON CA =? TM: EMERGENCE
Perhaps the question of sameness resides in whether either or both can be generative: can they re-write their own code.
The TM operates as an nth degree system through its states. But this does not make it generative unless it provides a facility for self-change of the algorithm.
Although the manner of rule set expression in the CA initially appears to be single degree, it is probably an nth degree system with each rule set box analogous to a state. Neither single nor nth degree implies the generative ability of self-change.
If both the TM and CA operate as nth degree systems, no functional dissimilarity is implied. If one is nth degree and the other single degree, that alone does not make their broad conceptual function dissimilar.
If their conceptual definitions permit one and not the other to re-write its code while operating, then they are not equivalent.
If neither or both can re-write code, they are equivalent.
Post a Comment