# A query regarding equivalence of Parallel vs. Serial cells Turning Machine

Given: A Turing machine (set of programs) that behaves as follows:

1. It has some fixed number of states $$(S)$$ and binary alphabet $$(0/1)$$.
2. For some constants $$k, p, (k:
• Its read/write head reads, writes, moves (left or right) $$k$$ cells at a time. Thus, each $$k$$ cell is a single 'Block'.

• It read/write head has internal memory of size: $$p*k$$, thus it can store $$p$$ 'blocks' inside. This 'internal memory' is initialized by some values before the program starts running.

• Depending on the state of the TM it can read and write (from/to) internal memory (to/from) TM tape. Also, depending on state, it can erase, move (on this internal memory or Tape) 1 'block' at a time. Moreover, it can perform basic boolean operations ($$AND, OR, NOT, XOR, NAND$$) on these internal memory blocks and store results in the internal memory.

• For an input size $$N$$, It has polynomial running time $$N^c$$ (for some constant $$c$$). The machine always stops after this time, with the result of the computation written on the current 'block' on Tape (the block where the read/write head is pointing when it stops).

In essence its a ordinary Turing Machine but instead of working on 1 cell at a time it operates on a block of $$k$$ cells.

Query: What is the running time of an equivalent 'serialized' single tape Turing machine that runs on 1 cell at a time rather than $$k$$ cells and implements the above logic?

I am sure its a trivial question/theorem but has been ages since I studied TMs and I don't recall the result.