Given: A Turing machine (set of programs) that behaves as follows:
- It has some fixed number of states $(S)$ and binary alphabet $(0/1)$.
- For some constants $k, p, (k<N, p< N)$:
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.