0
$\begingroup$

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.

$\endgroup$

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.