Turing Machine with additional finite memory of size $n$

Question

The question itself:

Let us define a generalization of Turing Machines to include a finite memory of >size $n$.

We denote such a Turing Machine formally as:

$M_{mem} = (Q, Σ, γ, δ_{mem}, n, q_0, q_a, q_r)$

where all the definitions are identical to the standard Turing Machine except >that there is the finite memory size n and the transition function δmem. At each >step, the transition depends on the current state, the input on the tape and all the memory. The transition to the >next step can update the entire memory.

Formally: $δ_{mem} : Q × Γ × Γ^n → Q × Γ × Γ^n × {L, R}$.

Given a finite memory Turing Machine $M_{mem}$, define $formally$ a (standard) Turing Machine $M$ such that $L(M) = L(M_{mem})$. Namely, both Turing Machines accept the same language.

my approach

I am asked to give two different constructions of such a turing machine. The first way that I managed to come up with is to encode the memory into the states of the turing machine and I managed to do so. I thought that a second way to do it is to encode the memory into the tape itself by concating the string in the memory into the input char itself but this causes problems because the turing machine doesn't have access to the memory in such a way because it will write down the encoding and then move left or right so it won't see the encoding of the memory no more. please guide me with the second approach and/or suggest me another way to do it.

Answer 1

I don't think that you can "embed" the extra memory into the alphabet and "carry" it with the head moving around without a $|Q|$ blow-up (blow-up comparable to the one of approach 1).

So a (weird!) approach to keep the size of $|Q|$ low, that can work is the following:

• embed both the extra memory and $Q$ into the alphabet $\Gamma_M = \{H,h\} \times Q \times \Gamma \times \Gamma^n$
• use only ONE cell (marked with embedded symbol $H$) to represent the current state of $M_{mem}$ + symbol under its head + the content of the extra-memory
• use some additional states to SHIFT the tape around the cell $H$

Very informally you have:

                  q1
                  S
....0 1  1 1 0 0 [0] 1 1 0 0 0 ...
    h h  h h h h  H  h h h h h 
                  ^
                  q_sim

In this condition, the (standard) Turing machine $M$ is on state $q_{sim}$ and is on symbol $\langle H,q_1,0,S \rangle$ that represents: head of $M_{mem}$ is on state $q1$, reading a $0$ and the content of the extra memory is $S$

Now if $M_{mem}$ writes a 1, writes $S'$ on the extra memory, moves $L$eft and enters $q_2$; the standard $M$ on state $q_{sim}$ writes $\langle H,q_2,1,S' \rangle$ and enters a sequence of states $q_{r_1},...,q_{r_k}$ that shift the whole tape one cell to the right and returns back on the cell marked with $H$ and state $q_{sim}$; simulating in this way the movement of the $M_{mem}$'s head:

                  q2
                  S'
....  0 1  1 1 0 [0] 1 1 1 0 0 0 ... << tape shifted right
      h h  h h h  H  h h h h h h 
                  ^
                  q_sim

Note that the standard $M$ simulates $M_{mem}$ transitions using only a single state $q_{sim}$ (plus two extra-states for accept/reject).

Also note that the symbol corresponding to the extra memory $S'$ is NOT MOVED, so the total number of states of $Q_M$ required to shift the "underlying" tape (simulating the move of the head of $M_{mem}$) depends only on $\Gamma$, not on $n$:

$\Gamma_M = \{H, h\} \times Q \times \Gamma \times \Gamma^n $

$\delta_M = Q_M \times \Gamma_M \to Q_M \times \Gamma_M \times \{L,R\}$

and $|Q_M| = k |\Gamma|+c$

You can also choose to embed the states of $M_{mem}$ into $Q_M$: in this case the alphabet is: $\Gamma_M = \{H, h\} \times \Gamma \times \Gamma^n $, but you must use more states: $|Q_M| = k |Q| |\Gamma|+c$

The above construction can also be generalized to standard Turing machines and (very informally) it roughly represents a switch from:

$\delta : Q \times \Gamma \to Q \times \Gamma \times \{L,R\}$ to

$\delta : \Gamma \times Q \to \Gamma \times Q \times \{L,R\}$