My instinctual response is that it is possible, but I can't see how to simulate the oracle tape on a 1-d CA.

If not, are they able to be simulated on n-dimensional CA? My thought is that the oracle tape could be simulated on another row in, say, a 2+1-dimensional cellular automaton.

  • $\begingroup$ are you limited in the kernel size and/or number of states? $\endgroup$ – ratchet freak Nov 21 '17 at 17:10
  • $\begingroup$ Do I interpret kernel size as the number of non-quiescent initial cells here? Also, can you explain why the number of states matters here? $\endgroup$ – adamcatto Nov 21 '17 at 17:21
  • $\begingroup$ I think I can answer your question once my confusions are clarified. $\endgroup$ – adamcatto Nov 21 '17 at 17:21
  • $\begingroup$ kernel size is how far each cell looks to decide it's next state. $\endgroup$ – ratchet freak Nov 21 '17 at 17:23
  • $\begingroup$ ah, I see. I think finite fixed kernel size implies inability to simulate an oracle machine, no? and I think we require at least 9 symbols, representing 0, 1, left, right, tape head, oracle tape head, ask, response, halt $\endgroup$ – adamcatto Nov 21 '17 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.