3
$\begingroup$

This question is a follow up to the question: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines.

To simulate a CA with a TM, I used a construction which placed a marker on the ends of the input, and modeled each "step" with the transition function. Assuming that $\rho(\text{''blank''}, \text{''blank''}, \text{''blank''}) = \text{''blank''}$, what is the time complexity of simulating a CA? I'm only concerned with the upper bound.

I'm really stuck, any hints would be really appreciated.

Edit: As recommended, I am adding a better description of the algorithm:

On input $w = w_1 w_2 \dots w_n$, have the TM place unique begin and end characters on each side of the input. We model a single timestamp in the CA by multiple steps of the TM. The head sweeps through the taps, replacing its contents with the contents of the CA tape in the next timestamp. We write each character one place to teh right of where it would have been in the CA. Formally, this is:

there are states $q_{a,b}$ for all pairs of CA states, with transitions in the form: $$ q_{a,b} \to^{c \to \rho(a, b, c), R} q_{b,c}$$

after completing a single sweep, return the head to the start of the tape and repeat. Continue unless an accept character is written, in which case, enter the TM accept state.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ What have you tried so far? Have you tried to write an algorithm to simulate a CA? What does it look like? Can you work out how much time it would take to implement each step of that algorithm on a Turing machine? $\endgroup$
    – D.W. ♦
    Commented Nov 20, 2013 at 3:02
  • $\begingroup$ @D.W. Yes, I have written an algorithm to simulate a Turing Machine. Would it be helpful if I made an edit to summarize my construction? I just didn't want to clutter the question. $\endgroup$
    – Kevin G
    Commented Nov 20, 2013 at 3:05
  • $\begingroup$ @D.W. The part I am having difficulty with is reasoning about the time complexity of the algorithm. I guess I'm having trouble wrapping my head around the idea of the time complexity of a machine simulating a machine. $\endgroup$
    – Kevin G
    Commented Nov 20, 2013 at 3:06
  • 1
    $\begingroup$ KevinG, great! Yeah, writing out your algorithm might help, if you want help in evaluating it runtime. As far as what it means to count the time complexity of this, you can start by upper-bounding the running time for the TM to emulate/perform a single transition of the CA (a single time step) -- and express this running time as a function of $n$, the number of cells in the cellular automaton that are currently non-blank (i.e., $n$ is the length of the input). $\endgroup$
    – D.W. ♦
    Commented Nov 20, 2013 at 3:36
  • 1
    $\begingroup$ OK, good! I see that your algorithm involves doing a sequence of sweeps. So, how many sweeps do you, in total? Next question: How many steps of TM-execution does each sweep take? (For instance, moving the head of the TM right one position takes one step of execution, so if it has to move $n$ positions to the left or right, that will take $n$ time steps.) Once you can answer those two questions, you can multiply those two quantities and you'll have a first cut at a time bound. $\endgroup$
    – D.W. ♦
    Commented Nov 20, 2013 at 4:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.