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<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.


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.