Is it possible to "unshift" onto a queue using this theoretical "queue automaton"?

Question

I have been playing Manufactoria, a game in which one has to build a production line that tests/modifies "robots". Each robot has a "tape" where each cell is colored either red, green, blue or yellow. The production line can test/modify a robot by popping colors off the start of its tape, by moving the robot to different lines depending on the color popped off, and by pushing more colors onto the end of its tape. The tape is effectively a queue.

One level ("Robostilts") asks you, the designer, to build a production line that modifies each robot's tape to put a "green" at the start, and a "yellow" at the end. It turns out this challenge is easily completed because all robots start with only red and blue colors on the tape, and no green or yellows.

However, I initially misinterpreted the challenge, thinking that the input tapes were completely arbitrary. This seemed challenging, and now I think it's impossible. However, I don't know how to show this precisely, but I thought someone here might be able to. I have formalized the problem below.

$A$ is the four-letter alphabet $\{ R, G, B, Y \}$.

An automaton is $(S,sInit,sTerm,d)$ where

• $S$ is a set of states
• $sInit \in S$ is the initial state
• $sTerm \in S$ is the terminal state
• $d$ is a transition function $: (S \times A) \rightarrow (S \times A\star)$. (Note: $A\star$ denotes lists of $A$ elements.)

The automaton steps through a series of configurations $(s, x) \in (S \times A\star)$.

For a given "input string" $i \in A\star$, the initial configuration is $(sInit, i)$.

The function $step : (S \times A\star) \rightarrow (S \times A\star)$ is given by

$ step (s, [x] \mathbin{+\mkern-10mu+} xs) =\\ \qquad\mathbf{let}\quad(s', new) = d(s,x)\\ \qquad\mathbf{in}\quad(s', xs \mathbin{+\mkern-10mu+} new) $

The task is to define such a machine which, starting with configuration $(sInit, i)$ for an arbitrary $i$, after a finite number of applications of the step function, reaches configuration $(sTerm, [G] \mathbin{+\mkern-10mu+} i \mathbin{+\mkern-10mu+} [Y])$.

Is this possible? If yes, how? If no, why not?

Answer 1

Without any way of creating an unmistakeable marker on the tape, this is not possible. (As far as I recall (cannot check right now), the tape in Manufactoria is actually bounded, which would make a difference, but let us assume this is not the case.)

Let $i$ be any input string, and consider the computation of a given automaton on $i$, i.e. the sequence $(s_0,x_0),\dots,(s_n,x_n)$ with $s_0=sInit$, $x_0=i$, $s_n=sTerm$, and $(s_{j+1},x_{j+1}) = step((s_j,x_j))$. In iteration $j$, we read and remove the first letter $a_j$ of $x_{j-1}$ and append a word $u_j$; these first letters form a word $w=a_1\dots a_n$.

It is not hard to see that any input word which starts with $w$, i.e. $wv$ for some $v$, is indistinguishable from $i$ to our automaton: it reads the same letters as it would on $i$, and as a result goes through the same states and appends the same $u_j$, so that the resulting word at the end is $vu_1\dots u_n$. This will fail to have the required form for any $v$ not starting with $G$ (and many others as well).

Answer 2

Try to "rotate" the contents of the tape, moving colors from one end to the other. (I did not really read the full formalization in your question, so I might be completely off here).

This seems related to the question "How can one simulate a PDA with a FIFO queue PDA?", the simulation of a LIFO (stack) by a FIFO (queue).