Some results on time-varying and relativised cellular automata^*

^*This research was partially supported by a grant from the Department of Science and Technology, Government of India.

Abstract

Cellular automata (CA) are parallel language recognition devices. In this paper, the notion of a time-varying CA (TVCA) is introduced. In a TVCA, the transition function can vary with time, and the variation is controlled by a prespecified language. This language can be viewed as an oracle to which the TVCA makes implicit queries; thus TVCA provide a mechanism for defining relativised CA. In this paper, the recognition capabilities of CA and TVCA are compared. TVCA as relativised CA are formalised, and the power of this implicit query mechanism is compared with the traditional oracle access in Turing machines.

Keywords:

• Cellular automata
• Turing machines
• relativisations
• language recognition

C.R. Categories:

• F.l.l
• F.1.2
• F.4.3

^*This research was partially supported by a grant from the Department of Science and Technology, Government of India.

^*This research was partially supported by a grant from the Department of Science and Technology, Government of India.

Notes

^*This research was partially supported by a grant from the Department of Science and Technology, Government of India.