% Collatz word problem
% _*_iso-latin-1_*_
% \def\lastedit{2011-10-18 18:53:59 by stolfi}

\nonstopmode % PARA RODAR LATEX EM BATCH MODE
\documentclass[12pt,twoside]{article}

\usepackage{techrep-ic}
\usepackage{latexsym}
\usepackage{amssymb}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage[margin=1in]{geometry}

\input{macros-jsmath}

\let\o=\undef\relax

\newcommand{\eqt}[2]{\begin{equation}\label{#1}#2\end{equation}}
% \newcommand{\oL}{{\dashv}}
% \newcommand{\oR}{{\vdash}}
\newcommand{\oL}{\mbox{\texttt{<}}}
\newcommand{\oR}{\mbox{\texttt{>}}}

\newcommand{\oa}{\mbox{\texttt{A}}}
\newcommand{\ob}{\mbox{\texttt{B}}}
\newcommand{\oc}{\mbox{\texttt{C}}}

\newcommand{\o}[1]{\mbox{\texttt{#1}}}

% \newcommand{\ox}{\hbox{\tt \vrule width 1em height 1ex depth 0pt}}

\newcommand{\ox}{\hbox{\tt \raise 0.25ex\hbox to 0.5em{\hss${\scriptstyle \triangleright}$\hss}}}
\newcommand{\oy}{\hbox{\tt \raise 0.25ex\hbox to 0.5em{\hss${\scriptstyle \triangleleft}$\hss}}}

\newcommand{\toast}{\stackrel{\ast}{\to}}
\newcommand{\eto}{\mapsto}
\newcommand{\etoast}{\stackrel{\ast}{\eto}}

\newcommand{\tail}{\dashv}
\newcommand{\head}{\vdash}

\newcommand{\pll}{\parallel}

\newcommand{\bin}[1]{[#1]}
\newcommand{\enc}[1]{[\![#1]\!]}

\newcommand{\ter}[1]{\la #1 \ra}
\newcommand{\ret}[1]{\la #1 \ra^{\ast}}

\newcommand{\ent}[1]{\la\!\la#1\ra\!\ra}

\newcommand{\enp}[1]{[\![\![#1]\!]\!]}
\newcommand{\enq}[1]{\la\!\la\!\la#1\ra\!\ra\!\ra}

\newcommand{\val}[1]{\omega(#1)}
\newcommand{\lav}[1]{\omega^\ast(#1)}

\newcommand{\isp}{\psi}

\newcommand{\udl}[1]{\underline{\hbox{$#1$}}}

\begin{document}

%%% PÁGINA DE CAPA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
% Número do relatório
\TRNumber{017}

% DATA DE PUBLICAÇÃO (PARA A CAPA)
%
\TRYear{11} % Dois dígitos
\TRMonth{10} % Numérico, 01-12

% LISTA DE AUTORES PARA CAPA (sem afiliações).
\TRAuthor{Guido C.~S.~Araújo \and Jorge Stolfi}

% TÍTULO PARA A CAPA (use \\ para forçar quebras de linha).
\TRTitle{A word problem\\equivalent to the\\Collatz sequence problem}

\TRMakeCover

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nomes de autores ABREVIADOS e titulo ABREVIADO,
% para cabeçalhos em cada página.
%
\markboth{G.~G.~S.~Araújo and J.~Stolfi}{Collatz word problem}
\pagestyle{myheadings}
\thispagestyle{empty}

\title{A word problem equivalent\\to theCollatz sequence problem}

\author{%
  Guido C.~S.~Araújo\thanks{IC-UNICAMP \texttt{guido@ic.unicamp.br}} 
  \and
  Jorge Stolfi\thanks{IC-UNICAMP \texttt{stolfi@ic.unicamp.br}}
  \thanks{This work benefitted from grants by CNQp and FAPESP}
}

\date{}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract} 
  The Collatz (or Ulam) sequence of a positive integer $n$ starts with $c_0 = n$, and 
  its general term $c_{i+1}$ for $i\geq 0$ is $c_{i}/2$ is $c_i$ is even, 
  or $3c_i + 1$ if $c_i$ is odd. It is conjectured that the sequence 
  of every positive integer includes a term $c_i = 1$. 
  In this report we describe a word problem that is equivalent to the Collatz sequence problem.
  Namely, we define an essentially deterministic contex-sensitive grammar whose 
  derivations from a given initial word correspond to the terms 
  of a Collatz sequence or to intermediate states in the computation of those
  terms.  The Collatz sequence conjeture then can be restated
  as saying that a derivation from any
  valid initial word (that encodes a positive integer) eventually leads to a 
  specific word (that encodes the integer 1).  We also explore some variants of this
  model.
\end{abstract}

\section{Introduction}

  The \emph{Collatz sequence} of a positive number $n$ starts with $c_0
  = n$, and its general term $c_{i+1}$ for $i\geq 0$ is $c_{i}/2$ is
  $c_i$ is even, or $3c_i + 1$ if $c_i$ is odd. For example, the
  Collatz sequence of 6 is $(6,3,10,5,16,8,4,2,1,4,2,1,\dots)$ This
  sequence has been called also the \emph{Ulam}, \emph{Kakutani},
  \emph{Thwaites}, \emph{Hasse}, \emph{Syracuse}, or \emph{hailstone}
  sequence.
 
  The formula for the general term can be written also as $c_{i+1} = \psi(c_i)$
  for all $i\in\RN$, where
    \eqt{eq.rec1}{
      \psi(m) = 
        \left\{
          \begin{array}{ll}
            r       & \mbox{if $m = 2 r$ for some $r\in\RN$} \\
            6 r + 4 & \mbox{if $m = 2 r + 1$ for some $r\in\RN$}
          \end{array}
        \right.
    }
  The Collatz sequence of $1$ is periodic with period length 3,
  $(1,4,2,1,4,2,\ldots)$. The \emph{Collatz conjecture} states that
  the sequence of \emph{every} positive integer $n$ eventually reaches
  the value 1, and therefore eventually becomes this periodic sequence.
 
\subsection{Optimized sequence}  
  
  Since $6m + 4$ is always even, we can ``optimize''
  the Collatz recurrence by combining the odd-case step with the following inevitable
  even-case step. Namely, we define
  an \emph{optimized} Collatz sequence of a positive integer $n$ as being $d_0 = n$ 
  and $d_{i+1} = \phi(d_i)$ for all $i\in\RN$, where
    \eqt{eq.rec2}{
      \phi(m) = 
        \left\{
          \begin{array}{ll}
            r       & \mbox{if $m = 2 r$ for some $r\in\RN$} \\
            3 r + 2 & \mbox{if $m = 2 r + 1$ for some $r\in\RN$}
          \end{array}
        \right.
    }
  The optimized Collatz sequence of an integer $n$ 
  is identical to its standard sequence except for the omission
  of the even term that follows each odd term.  For example, the 
  optimized sequence of 6 is $(6,3,5,8,4,2,1,2,1,2,1,\dots)$
  
  It follows that the standard and optimized sequences are equivalent
  for the purposes of the conjecture; namely, the optimized sequence
  includes the integer 1 if and only if the standard sequence does.
  Therefore, we will work with the optimized
  recurrence~\eqref{eq.rec2} from now on.
  
\section{Word formulation}

\subsection{Basic grammar}

  We now define a context-sensitive grammar $G$ to model the Collatz
  recurrence function~\eqref{eq.rec2}. The alphabet is the set
  $\set{\o0,\o1,\oL,\oR,\oa,\ob,\oc}$. We will call
  $\Delta=\set{\o0,\o1}$ the set of \emph{bits}, $\Lambda =
  \set{\oL,\oR}$ the set of \emph{delimiters}, and $\Sigma =
  \set{\oa,\ob,\oc}$ the set of \emph{trits}. A \emph{word} is any
  string from $(\Delta\cup\Sigma\cup\Lambda)^\ast$; a \emph{valid}
  word is any word of the form $\oL \beta \oR$ where $\beta$ is a
  non-empty word in $(\Delta\cup\Sigma)^\ast$.
  
\subsection{Word values}

  Every word $\beta$ of $G$ is meant to encode a positive integer 
  $\val{\beta}$, according to the following rules:
    \eqt{eq.value}{
      \val{\beta} = 
        \left\{
          \begin{array}{ll}
            0               & \mbox{if $\beta$ is the empty string},\\
            \val{\gamma}    & \mbox{if $\beta = \oL \gamma$ or $\beta = \gamma\oR$},\\
            2\val{\gamma}   & \mbox{if $\beta = \gamma \o0$},\\
            2\val{\gamma}+1 & \mbox{if $\beta = \gamma \o1$},\\
            3\val{\gamma}   & \mbox{if $\beta = \gamma \oa$},\\
            3\val{\gamma}+1 & \mbox{if $\beta = \gamma \ob$},\\
            3\val{\gamma}+2 & \mbox{if $\beta = \gamma \oc$}.\\
          \end{array}
        \right.
    }
  Thus, for example, $\val{\o1\o1\o0} = 6$
  (and, in general, $\val{\bin{n}} = n$ for every $n$); 
  $\val{\o1\o1\o0\ob} = 3\cdot 6 + 1 = 19$; 
  and $\val{\oL \ob \o1 \oc\ob\oR} = 34$.
  The integer $\val{\beta}$ is called the \emph{primal value} or just the \emph{value} of $\beta$.
  In general, there are many strings in $(\Sigma\cup\Delta)^\ast$ with the same primal value.
  
  Observe that every string $\beta \in (\Sigma\cup\Delta)^{\ast}$ is the representation of the
  integer $\val{\beta}$ in a mixed base-2 and base-3 system, where the 
  trits $\oa$, $\ob$, and $\oc$ are interpreted as the ternary digits 0, 1, and 2, respectively. 
  Indeed, let $d(\beta)$ and $t(\beta)$ denote the number of bits and trits in $\beta$,
  respectively.  Let also $\beta \tail k$ and $k\head \beta$ denote the string $\beta$ truncated to the last $k$ symbols
  and to the first $k$ symbols, respectively.  Then if $\beta$ is a string $\tau_m\tau_{m-1}\cdots\tau_1\tau_0$, with 
  each $\tau_i\in\Sigma\cup\Delta$, we have
    \eqt{eq.valsum}{
      \val{\beta} = \sum_{i=0}^{m} \val{\tau_i}2^{b(\beta \tail i)}3^{t(\beta \tail i)}
    }
  More generally, for any $\alpha,\beta\in(\Sigma\cup\Delta)^\ast$,
    \eqt{eq.valsplit}{
      \val{\alpha\beta} = \val{\alpha}2^{b(\beta)}3^{t(\beta)} + \val{\beta}
    }
  It follows that, for any $\beta',\beta'',\gamma \in (\Sigma\cup\Delta)^\ast$,
    \eqt{eq.valeqn}{
      \val{\beta'} = \val{\beta''} \;\Leftrightarrow\; \val{\beta'\gamma} = \val{\beta''\gamma}
   }
  
\subsection{Dual values}

  The \emph{dual value} of a word $\beta$ is defined by the recurrences
    \eqt{eq.duval}{
      \lav{\beta} = 
        \left\{
          \begin{array}{ll}
            0               & \mbox{if $\beta$ is the empty string},\\
            \lav{\gamma}    & \mbox{if $\beta = \oL \gamma$ or $\beta = \gamma\oR$},\\
            2\lav{\gamma}   & \mbox{if $\beta = \o0 \gamma$},\\
            2\lav{\gamma}+1 & \mbox{if $\beta = \o1 \gamma$},\\
            3\lav{\gamma}   & \mbox{if $\beta = \oa \gamma$},\\
            3\lav{\gamma}+2 & \mbox{if $\beta = \ob \gamma$},\\
            3\lav{\gamma}+1 & \mbox{if $\beta = \oc \gamma$}.\\
          \end{array}
        \right.
    }
  In other words, the dual value is obtained by reversing the word (minus the delimiters)
  and reading it as a mixed-base representation of a number, with `$\o0$' and `$\o1$'
  as the base-2 digits, and `$\oa$', `$\ob$' and `$\oc$' as base-3 digits with
  values 0, 2, and 1, respectively.  Note that the values of `$\ob$' and `$\oc$' 
  in $\lav{\cdot}$ are swapped relative to its values in $\val{\cdot}$.
  
  The dual value has properties similar to those of the primal value, but reversed left-to-right.
  If $\beta$ is a string $\tau_0\tau_1\cdots\tau_{m-1}\tau_m$, with 
  each $\tau_i\in\Sigma\cup\Delta$, we have
    \eqt{eq.valsum}{
      \lav{\beta} = \sum_{i=0}^{m} \lav{\tau_i}2^{b(i \head \beta)}3^{t(i \head \beta)}
    }
  More generally, for any $\alpha,\beta\in(\Sigma\cup\Delta)^\ast$,
    \eqt{eq.valsplit}{
      \lav{\alpha\beta} = \lav{\alpha} + 2^{b(\alpha)}3^{t(\alpha)}\lav{\beta}
    }
  It follows that, for any $\beta',\beta'',\alpha \in (\Sigma\cup\Delta)^\ast$,
    \eqt{eq.valeqn}{
      \lav{\beta'} = \lav{\beta''} \;\Leftrightarrow\; \lav{\alpha\beta'} = \lav{\alpha\beta''}
    }
  Let $\ret{n}$ be the shortest base-3 representation of the integer $n$, using digits $\oa=0$,
  $\ob=2$, and $\oc=1$, reversed left-to-right.  Then $\lav{\ret{n}} = n$ for all integer $n$.
  
\subsection{Substitution rules}

  The productions (basic substitution rules) of $G$ are
    \eqt{eq.rules}{
      \begin{array}{rcl|rcl|rcl}
        \o0 \oR &\to& \oR   & \o1 \oR &\to& \oc \oR & ~ &~& ~ \\
        \o0 \oa &\to& \oa \o0 & \o1 \oa &\to& \ob \o1   & \oL \oa &\to& \oL     \\
        \o0 \ob &\to& \oa \o1 & \o1 \ob &\to& \oc \o0   & \oL \ob &\to& \oL \o1   \\
        \o0 \oc &\to& \ob \o0 & \o1 \oc &\to& \oc \o1   & \oL \oc &\to& \oL \ob \o0 \\
      \end{array}
    }
  We will write $\beta\toast \gamma$ if the word $\gamma$ can be
  obtained from the word $\beta$ by zero or more of these
  substitutions. 
  
  This grammar admits many derivations from a given initial word.  For example,
  starting with the word $\oL \o0 \ob \o1 \o0 \oR$ we can get, among many others,
  the two derivations below:
    \eqt{eq.derivs}{
      \begin{array}{lc|cl}
        \oL \udl{\o0 \ob} \o1 \o0 \oR    &\quad&\quad&   \oL \o0 \ob \o1\udl{\o0 \oR} \\
        \udl{\oL \oa} \o1 \o1 \o0 \oR    &\quad&\quad&   \oL \o0 \ob \udl{\o1 \oR} \\
        \oL \o1 \o1 \udl{\o0 \oR}        &\quad&\quad&   \oL \udl{\o0 \ob} \oc \oR \\
        \oL \o1 \udl{\o1 \oR}            &\quad&\quad&   \oL \oa \udl{\o1 \oc} \oR \\
        \oL \udl{\o1 \oc} \oR            &\quad&\quad&   \oL \oa \oc \udl{\o1 \oR} \\
        \udl{\oL \oc} \o1 \oR            &\quad&\quad&   \udl{\oL \oa} \oc \oc \oR \\
        \udl{\oL \ob} \o0\o1 \oR         &\quad&\quad&   \udl{\oL \oc} \oc \oR \\
        \oL \o1\o0\udl{\o1 \oR}          &\quad&\quad&   \oL \ob \udl{\o0 \oc} \oR \\
        \oL \o1\udl{\o0\oc} \oR          &\quad&\quad&   \oL \ob \ob \udl{\o0 \oR} \\
        \oL \udl{\o1\ob} \o0 \oR         &\quad&\quad&   \udl{\oL \ob} \ob \oR \\
        \udl{\oL \oc} \o0 \o0 \oR        &\quad&\quad&   \oL \udl{\o1 \ob} \oR \\
        \udl{\oL \ob} \o0 \o0 \o0 \oR    &\quad&\quad&   \oL \oc \udl{\o0 \oR} \\
        \oL \o1 \o0 \o0 \udl{\o0 \oR}    &\quad&\quad&   \udl{\oL \oc} \oR \\
        \oL \o1 \o0 \udl{\o0 \oR}        &\quad&\quad&   \oL \ob \udl{\o0 \oR} \\
        \oL \o1 \udl{\o0 \oR}            &\quad&\quad&   \udl{\oL \ob} \oR \\
        \oL \udl{\o1 \oR}                &\quad&\quad&   \oL \udl{\o1 \oR} \\
        \udl{\oL \oc} \oR                &\quad&\quad&   \udl{\oL \oc} \oR \\
        \udl{\oL \ob} \o0 \oR            &\quad&\quad&   \oL \ob \udl{\o0 \oR} \\
        \oL \o1 \udl{\o0 \oR}            &\quad&\quad&   \udl{\oL \ob} \oR \\
        \oL \udl{\o1 \oR}                &\quad&\quad&   \oL \udl{\o1 \oR} \\
        \udl{\oL \oc} \oR                &\quad&\quad&   \udl{\oL \oc} \oR \\
        \udl{\oL \ob} \o0 \oR            &\quad&\quad&   \oL \ob \udl{\o0 \oR} \\
        \oL \o1 \udl{\o0 \oR}            &\quad&\quad&   \udl{\oL \ob} \oR \\
        \oL \udl{\o1 \oR}                &\quad&\quad&   \oL \udl{\o1 \oR} \\
        \udl{\oL \oc} \oR                &\quad&\quad&   \udl{\oL \oc} \oR \\
        \udl{\oL \ob} \o0 \oR            &\quad&\quad&   \oL \ob \udl{\o0 \oR} \\
        \vdots                           &\quad&\quad&   \vdots
      \end{array}
    } 
  The substitutions of table~\ref{eq.rules} can be justified by their
  effect on word values. It can be seen that,
  except for the two entries of the first row, every entry in the table
  preserves the value of the word. Namely, each application of one
  of those substitutions has the form  
    \eqt{eq.astep1}{
      \oL \beta \delta \sigma \gamma \oR \;\to\;
      \oL \beta \sigma' \delta'\gamma \oR
    }
  or
    \eqt{eq.astep2}{
      \oL \sigma \gamma \oR \;\to\;
      \oL \beta' \gamma \oR
    }
  for words $\beta,\gamma,\beta'\in(\Sigma\cup\Delta)^\ast$, trits $\sigma,\sigma'\in\Sigma$,
  and bits $\delta,\delta'\in\Delta$. In the first case we can check that
    \eqt{eq.astep1e}{
      \val{\beta \sigma' \delta'} = \val{\beta \delta \sigma}
    }
  In the second case,
    \eqt{eq.astep2e}{
      \val{\beta'} = \val{\sigma}
    }
  Since the old and new prefixes have the same value, and the suffix $\gamma\oR$ is unchanged,
  the value of the entire word is preserved.
  On the other hand, the two substitutions in the first row of table~\ref{eq.rules} do change the
  word's value. Applied to whole words, they are
    \eqt{eq.astep1f}{
      \oL \beta \o0 \oR \;\to\;
      \oL \beta \oR
    }
  and
    \eqt{eq.astep2f}{
      \oL \beta \o1 \oR \;\to\;
      \oL \beta \oc \oR
    }
  Let $r=\val{\beta}$; in the first case, the (even) word value
  $\val{\beta \o0} = 2\val{\beta} = 2 r$ is replaced by $\val{\beta} =
  r$. In the second case, the (odd) word value $\val{\beta 1} = 2 r +
  1$ is replaced by $\val{\beta\oc} = 3\val{\beta}+2 = 3 r + 2$.
  Comparing with formulas~\eqref{eq.rec2}, we conclude that every time
  one of these two rules is applied, the value of the word changes
  from $m$ to $\phi(m)$.
  
  Finally, observe that the substitutions that do not change the value
  either decrease the number of trits, or reduce the
  lexicographic rank of the word (assuming bits are sorted before
  trits). Therefore, any derivation in $G$ that starts from any
  finite valid word must eventually use one of those two value-changing
  rules.
  
  We conclude that, in any derivation of the grammar $G$, the values
  of successive words will form the Collatz sequence of the value of
  the starting word; except that each element of the latter may be
  repeated some finite number of times.
  
\subsection{The Ztalloc sequence}

  One can check that every production of the form $\delta\oR \to \gamma$ or $\delta\sigma \to \gamma$,
  with $\delta\in\Delta$ and $\sigma\in\Sigma$, preserves the dual value of the word.
  On the other hand, the substitutions at the left end change the dual value $m$ to $\isp(m)$,
  where
    \eqt{eq.rec1}{
      \isp(m) = 
        \left\{
          \begin{array}{lcll}
            r       &=& m/3      & \mbox{if $m = 3 r$ for some $r\in\RN$} \\
            6 r + 2 &=& 2m       & \mbox{if $m = 3 r + 1$ for some $r\in\RN$}\\
            2 r + 1 &=& (2m-2)/3 & \mbox{if $m = 3 r + 2$ for some $r\in\RN$}
          \end{array}
        \right.
    }
  The sequence of values obtained by this recurrence from a starting integer $n$
  is a dual of the Collatz sequence, which we will call the \emph{Ztalloc sequence of $n$}
  for lack of a better name.  The sequence of 16, for example,
  is $(16,32,21,7,14,9,3,1,2,1,2,\ldots)$.
  
  The Collatz conjecture can be stated also for the Ztalloc sequence, and the 
  model above shows that the two are equivalent: one sequence includes the integer 1
  if and only if the other sequence does.
  
  One can define a \emph{double recurrence} over the pairs of positive integers,
  by the formula $(m,n) \mapsto (\psi(n),\isp(n))$. 

\section{Greedy derivation}

  The left column of table~\eqref{eq.derivs} is an example of a
  \emph{greedy} derivation, where each step is determined by the
  following rule: if the word contains any of the trits
  $\set{\oa,\ob,\oc}$, then apply to the leftmost trit occurrence
  the (unique) value-preserving substitution that can be applied to
  it; otherwise, use the (unique) value changing substitution.
  
  Note that a greedy derivation is completely determined by the
  starting word. We will write $\beta \eto \gamma$ if $\gamma$ can
  be obtained from $\beta$ in a single greedy step, and $beta\etoast
  \gamma$ if it can be obtained in zero or more such steps.
  
  If a valid word contains one or more trits, the unique
  greedy derivation step that can be applied to it either eliminates
  one trit, or preserves the number of trits and reduces the
  number of bits to the left of the first trit. In either case
  the value of the word is preserved. Therefore,
  starting from an arbitrary valid word $\beta$, a greedy derivation
  will eventually arrive to a trit-free word $\oL \bin{m} \oR$,
  all the while preserving the word's value $m=\val{\beta}$.  Then the next
  greedy derivation step will either remove a final $\o0$ from $\bin{m}$,
  or replace its final $\o1$ by the $\oc$ trit; in either case changing the 
  word's value from $m$ to $\phi(m)$. 
  
  When using greedy derivation, it is convenient to start with a word of the form 
  $\enc{n} = \oL \bin{n} \oR$ where $n$ is a positive integer and
  $\bin{n}$ is its base-2 encoding without leading zeros. Thus, for
  example, $\enc{1} = \oL \o1 \oR$, $\enc{2} = \oL \o1\o0 \oR$, and
  $\enc{19} = \oL \o1\o0\o0\o1\o1 \oR$.
  
  If a greedy derivation starts from $\enc{n}$,
  then every word in it will contain at most one trit. Let
  $\beta_0$, $\beta_1$, \dots be the trit-free words that occur in
  the derivation. We conclude that the sequence $w(\beta_i)$ is the
  (optimized) Collatz sequence of the integer $n$.  For example,
  a greedy derivation for $n = 6$ would be
    \eqt{eq.eder}{
      \begin{array}{lcrr}
        \beta                            &\quad&  \val{\beta} & \lav{\beta}\\
        \hline
        \oL \o0 \o1 \udl{\o0 \oR}        &\quad&   6      &   \\
        \oL \o1 \udl{\o1 \oR}            &\quad&   3      &   \\
        \oL \udl{\o1 \oc} \oR            &\quad&   5      &   \\
        \udl{\oL \oc} \o1 \oR            &\quad&   5      &   \\
        \udl{\oL \ob} \o0 \o1 \oR        &\quad&   5      &   \\
        \oL \o1 \o0\udl{\o1 \oR}         &\quad&   5      &   \\
        \oL \o1\udl{\o0 \oc} \oR         &\quad&   8      &   \\
        \oL \udl{\o1 \ob} \o0 \oR        &\quad&   8      &   \\
        \udl{\oL \oc} \o0 \o0 \oR        &\quad&   8      &   \\
        \udl{\oL \ob} \o0 \o0 \o0 \oR    &\quad&   8      &   \\
        \oL \o1 \o0 \o0 \udl{\o0 \oR}    &\quad&   8      &   \\
        \oL \o1 \o0 \udl{\o0 \oR}        &\quad&   4      &   \\
        \oL \o1 \udl{\o0 \oR}            &\quad&   2      &   \\
        \oL \udl{\o1 \oR}                &\quad&   1      &   \\
        \udl{\oL \oc} \oR                &\quad&   2      &   \\
        \udl{\oL \ob} \o0 \oR            &\quad&   2      &   \\
        \oL \o1 \udl{\o0 \oR}            &\quad&   2      &   \\
        \oL \udl{\o1 \oR}                &\quad&   1      &   \\
        \udl{\oL \oc} \oR                &\quad&   2      &   \\
        \udl{\oL \ob} \o0 \oR            &\quad&   2      &   \\
        \oL \o1 \udl{\o0 \oR}            &\quad&   2      &   \\
        \oL \udl{\o1 \oR}                &\quad&   1      &   \\
        \udl{\oL \oc} \oR                &\quad&   2      &   \\
        \udl{\oL \ob} \o0 \oR            &\quad&   2      &   \\
        \vdots                           &\quad&   \vdots&   \vdots
      \end{array}
    }
  We remark that the last rule in the last row of table~\eqref{eq.rules},
  $\oL \oc \to \oL \ob \o0$, could be replaced by $\oL \oc \to \oL \o1 \o0$,
  since the $\ob$ must necessarily change to $\o1$ at some point.  This optimization
  would save a few steps in greedy derivations, and simplify some of the argument;
  however, it would considerably complicate the definition and analysis of section~\ref{s.lazy}.

\section{Lazy derivations}
\label{s.lazy}

  The right column of table~\eqref{eq.derivs} is an example of a
  \emph{lazy} derivation, defined by the following rule: if the word
  contains any bits, use the (unique) substitution from the first
  two columns of table~\eqref{eq.rules} that can be applied as far to
  the right as possible; otherwise apply the (unique) substitution from
  the third column that can be used to the delimiter `$\oL$'.
  
  In a lazy derivation, if a valid word contains any bits, the 
  next step either reduces the number of bits, or preserves the 
  number of bits but reduces the number of trits to the 
  right of the last bit.  Therefore, starting from any valid word,
  a lazy derivation will eventually produce a bit-free word. 
  The previous step (if any), that eliminated the last digi,
  must have used a substitution from the first row of table~\eqref{eq.rules},
  and therefore must have changes the word's value from some integer $m$
  to $\phi(m)$.  The word values will then remain unchanged until the
  next bit-free word.
  
  In view of this observation, for the study of lazy derivations it is conventient to
  start with a \emph{lazy encoding} of a positive integer $n$, which
  is a valid bit-free word $\ent{n}$ whose value is $n$. Namely 
  we define $\ent(n) = \oL \ter{n} \oR$, where $\ter{n}$ is the
  representation of $n$ in base 3 using the trits $\oa$, $\ob$, and $\oc$ 
  as digits with values 0, 1, and 2, respectively, without any leading $\oa$. 
  For example, $\ent{1} = \oL \ob\oR$, and $\ent{19} = \oL \ob\oa\oc\oR$ (since 
  $19 = (102)_{3}$). 
  
  In lazy derivation of $G_1$ that starts with a lazy encoding $\ent{n}$,
  every word will contain at most one bit.  as before, let $\beta_0$, $\beta_1$, 
  $\beta_2$, \dots be the bit-free words in the derivation. Their values 
  will be the (optimized) Collatz sequence of $n$.  For example, the lazy derivtion
  of $\ent{6} = \oL \oc\oa \oR$ is 
   \eqt{eq.lder}{
      \begin{array}{lcrr}
        \beta                        &\quad&   \val{\beta} & \lav{\beta}\\
        \hline
        \udl{\oL \oc} \oa \oR        &\quad&   6     &   \\
        \oL \ob \udl{\o0 \oa} \oR    &\quad&   6     &   \\
        \oL \ob \oa \udl{\o0 \oR}    &\quad&   6     &   \\
        \udl{\oL \ob} \oa \oR        &\quad&   3     &   \\
        \oL \udl{\o1 \oa} \oR        &\quad&   3     &   \\
        \oL \ob \udl{\o1 \oR}        &\quad&   3     &   \\
        \udl{\oL \ob} \oc \oR        &\quad&   5     &   \\
        \oL \udl{\o1 \oc} \oR        &\quad&   5     &   \\
        \oL \oc \udl{\o1 \oR}        &\quad&   5     &   \\
        \udl{\oL \oc} \oc \oR        &\quad&   8     &   \\
        \oL \ob \udl{\o0 \oc} \oR    &\quad&   8     &   \\
        \oL \ob \ob \udl{\o0 \oR}    &\quad&   8     &   \\
        \udl{\oL \ob} \ob \oR        &\quad&   4     &   \\
        \oL \udl{\o1 \ob} \oR        &\quad&   4     &   \\
        \oL \oc \udl{\o0 \oR}        &\quad&   4     &   \\
        \udl{\oL \oc} \oR            &\quad&   2     &   \\
        \oL \ob \udl{\o0 \oR}        &\quad&   2     &   \\
        \udl{\oL \ob} \oR            &\quad&   1     &   \\
        \oL \udl{\o1 \oR}            &\quad&   1     &   \\
        \udl{\oL \oc} \oR            &\quad&   2     &   \\
        \oL \ob \udl{\o0 \oR}        &\quad&   2     &   \\
        \udl{\oL \ob} \oR            &\quad&   1     &   \\
        \oL \udl{\o1 \oR}            &\quad&   1     &   \\
        \udl{\oL \oc} \oR            &\quad&   2     &   \\
        \oL \ob \udl{\o0 \oR}        &\quad&   2     &   \\
        \udl{\oL \ob} \oR            &\quad&   1     &   \\
        \oL \udl{\o1 \oR}            &\quad&   1     &   \\
        \vdots                       &\quad&   \vdots&   \vdots
      \end{array}
    }
  One can view the lazy derivation as a dual of the greedy derivation,
  where the bits and trits change roles, and the computation of 
  the $\phi$ function proceeds in opposite directions. 

\section{Parallel derivation}

  One can increase the ``efficiency'' of this model by carrying
  out all applicable substitutions in parallel.
  
  For this purpose we define an \emph{alternating} word as a string with one of
  the forms
    \eqt{eq.vawEx}{
      \begin{array}{rlcl}
                \oL&\delta_1\sigma_1\delta_2\sigma_2\cdots \delta_{k-1}\sigma_{k-1}\oR           &\quad& [{-}:{-}] \\
                \oL&\delta_1\sigma_1\delta_2\sigma_2\cdots \delta_{k-1}\sigma_{k-1}\delta_{k}\oR &\quad& [{-}:{+}] \\
        \oL\sigma_0&\delta_1\sigma_1\delta_2\sigma_2\cdots \delta_{k-1}\sigma_{k-1}\oR           &\quad& [{+}:{-}] \\
        \oL\sigma_0&\delta_1\sigma_1\delta_2\sigma_2\cdots \delta_{k-1}\sigma_{k-1}\delta_{k}\oR &\quad& [{+}:{+}]
      \end{array}
    }
  for some $k>0$, except $\oL\oR$, where each
  symbol $\delta_i$ is in $\Delta$ and each $\sigma_i$ is in $\Sigma$.
  We also define the \emph{parallel encodings} $\enp{n}$ and $\enq{n}$ of a positive integer $n$
  to be shortest alternating words that end with a bit or trit, respectively,
  whose value is $n$.  For example:
    \eqt{eq.encEx}{
      \begin{array}{rclcrcl}
        \enp{1}  &=& \oL \o1 \oR              &\quad&  \enq{1}  &=& \oL \ob \oR \\                        
        \enp{6}  &=& \oL \o1 \oa \o0 \oR      &\quad&  \enq{6}  &=& \oL \ob 0 \oa \oR  \\              
        \enp{19} &=& \oL \ob \o1 \oa \o1 \oR  &\quad&  \enq{19} &=& \oL 1 \oa 0 \ob \oR \\
        \enp{34} &=& \oL \oc \o1 \oc \o0 \oR  &\quad&  \enq{34} &=& \oL 1 \oc 1 \ob \oR  \\
      \end{array}
    }
  A \emph{parallel derivation} is a sequence of alternating
  words, where each new word is derived from the preceding one by a
  \emph{parallel derivation step}; which
  consists of parsing the current word in one of the forms~\eqref{eq.vawEx},
  applying the appropriate substitution to each of the pairs
  `$\oL \sigma_0$', `$\delta_k\oR$', and `$\delta_i\sigma_i$' for $i\in\set{1\dd k-1}$,
  and concatenating the resulting strings.  
  
  Note that, for each of those symbol pairs, there is exactly one rule
  in table~\eqref{eq.rules} that can be applied. For the internal
  pairs $\delta_i\sigma_i$ of any form, this operation replaces a
  string in $\Delta\Sigma$ by a string in $\Sigma\Delta$. If the word
  is of the form $[{+}:{-}]$ or $[{+}:{+}]$, the
  initial pair $\oL \sigma_0$ is replaced by `$\oL$' or by a pair in
  $\oL \Delta$ or in $\oL\Sigma\Delta$; otherwise the initial `$\oL$'
  is not substituted. If the word is of the form $[{-}:{+}]$ or
  $[{+}:{+}]$, the last pair $\delta_{k}\oR$ is replaced by
  just $\oR$ or by a pair in $\Sigma\oR$; otherwise the final `$\oR$'
  is not substituted.
  
  In any case the result of a parallel derivation step is an alternating word.
  Moreover, if the word is of the form $[{-}:{+}]$ or $[{+}:{+}]$
  its value is changed from $m$ to $\phi(m)$; otherwise its value remains unchanged.
  Therefore, if we start with either $\enp{n}$ or $\enq{n}$, the values of
  the words in the parallel derivation will include all the terms of
  the (optimized) Collatz sequence, with occasional repetitions.  For example:
   \eqt{eq.pder}{
      \begin{array}{lcccrr}
        \beta                                      &\quad&   \mbox{Type}   &\quad& \val{beta}\\
        \hline
        \udl{\oL \,\ob} \,\udl{\o0 \,\oa} \,\oR    &\quad&   [{+}:{-}]    &\quad& 6 &  \\
        \oL \,\udl{\o1 \,\oa} \,\udl{\o0 \,\oR}    &\quad&   [{-}:{+}]    &\quad& 6 &  \\
        \udl{\oL \,\ob} \,\udl{\o1 \,\oR}          &\quad&   [{+}:{+}]    &\quad& 3 &  \\
        \oL \udl{\o1 \,\oc} \,\oR                  &\quad&   [{-}:{-}]    &\quad& 5 &  \\
        \udl{\oL \,\oc} \,\udl{\o1 \,\oR}          &\quad&   [{+}:{+}]    &\quad& 5 &  \\
        \udl{\oL \,\ob} \,\udl{\o0 \,\oc} \,\oR    &\quad&   [{+}:{-}]    &\quad& 8 &  \\
        \oL \,\udl{\o1 \,\ob} \,\udl{\o0 \,\oR}    &\quad&   [{-}:{+}]    &\quad& 8 &  \\
        \udl{\oL \,\oc} \,\udl{\o0 \,\oR}          &\quad&   [{+}:{+}]    &\quad& 4 &  \\
        \udl{\oL \,\ob} \,\udl{\o0 \,\oR}          &\quad&   [{+}:{+}]    &\quad& 2 &  \\
        \oL \,\udl{\o1 \,\oR}                      &\quad&   [{-}:{+}]    &\quad& 1 &  \\
        \udl{\oL \,\oc} \,\oR                      &\quad&   [{+}:{-}]    &\quad& 2 &  \\
        \udl{\oL \,\ob} \,\udl{\o0 \,\oR}          &\quad&   [{+}:{+}]    &\quad& 2 &  \\
        \oL \,\udl{\o1 \,\oR}                      &\quad&   [{-}:{+}]    &\quad& 1 &  \\
        \udl{\oL \,\oc} \,\oR                      &\quad&   [{+}:{-}]    &\quad& 2 &  \\
        \udl{\oL \,\ob} \,\udl{\o0 \,\oR}          &\quad&   [{+}:{+}]    &\quad& 2 &  \\
        \oL \,\udl{\o1 \,\oR}                      &\quad&   [{-}:{+}]    &\quad& 1 &  \\
        \udl{\oL \,\oc} \,\oR                      &\quad&   [{+}:{-}]    &\quad& 2 &  \\
        \udl{\oL \,\ob} \,\udl{\o0 \,\oR}          &\quad&   [{+}:{+}]    &\quad& 2 &  \\
        \vdots                                     &\quad&   \vdots       &\quad& \vdots & \vdots
      \end{array}
    }
  
\section{Macro-symbols}

  We can further ``speed up'' the model by grouping bits and trits
  into macro-symbols, and defining a grammar that operates on
  groups rather than individual bits .
  
  First we choose a \emph{binary suffix code} $\CB$; that is, a finite
  set $H$ of strings in $\Delta^{+}$ such that every bit string in
  $\Delta^{+}$ is a suffix of some word in $\CB$, or has a unique
  suffix that is in $\CB$. A trivial example of binary suffix code is
  the set $\Delta^k$ of all the bit strings with a fixed length $k$.
  Another example is the set $C =
  \set{\o0\o0,\o0\o1\o0,\o1\o1\o0,\o1}$. Basically, a binary suffix
  code is the set of leaf-to-root paths from in any finite binary
  tree. Any string $\delta$ of $\Delta^{*}$ can be parsed into a
  concatenation $\alpha \delta_1\delta_2\cdots\delta_r$, for some
  $r\geq 0$, where each $\delta_i$ is a code word of $\CB$ and
  $\alpha$ is a proper suffix (possibly empty) of a code word. We call
  this decomposition the \emph{suffix $\CB$-parsing} of $\delta$.
  
  We also choose a \emph{ternary prefix code} $\CT$; that is, a finite
  set $\CT$ of strings in $\Sigma^{+}$ such that every bit string in
  $\Sigma^{+}$ a prefix of some word in $\CT$, or has a unique prefix
  that is in $\CT$. A trivial example of ternary prefix code is the
  set $\Sigma^k$ of all the trit strings with a fixed length $k$.
  Another example is the set $C =
  \set{\oa\oa\oa,\oa\oa\ob,\oa\oa\oc,\oa\ob,\oa\oc,\ob,\oc}$.
  Basically, a ternary prefix code is the set of root-to-leaf paths
  from in any finite ternary tree. Any string $\sigma$ of $\Sigma^{*}$
  be parsed into a concatenation
  $\sigma_1\sigma_2\cdots\sigma_s\beta$, where each $\sigma_i$ is a
  code word of $\CT$ and $\beta$ is a proper prefix (possibly empty)
  of a code word. We call this decomposition the \emph{prefix
  $\CT$-parsing} of $\sigma$.
  
  By definition, the individual symbols in the new grammar $G'$
  comprise the delimiters $\oL$ and $\oR$, a set of \emph{macro-bits}
  or \emph{bytes} $\Delta'$, and a set of \emph{macro-trits} or
  \emph{trytes} $\Sigma'$. The bytes $\Delta'$ are the words of $\CB$
  and all its non-empty proper suffixes; the trytes $\Sigma'$ are the words of
  $\CT$ and all their non-empty proper prefixes. In both cases, each word is
  treated as single symbol of $G'$. For clarity, when writing a word
  of $G'$ we will use parentheses to delimit individual bytes and trytes.
  
  For $G'$, the notation $\bin{n}$ is redefined to mean the suffix
  $\CB$-parsing of the binary representation of $n$, left-padded with
  zeros as needed so that the first term is a complete code word;
  where each term of the parsing is considered a separate macro
  symbol. For example, if we use the code $\Delta^3$, then $[19]$ is
  the word $(\o0\o1\o0)(\o0\o1\o1)$, with two bytes $\o0\o1\o0$ and
  $\o0\o1\o1$. If we use the code $C$ above, $[19] =
  (\o1)(\o0\o0)(\o1)(\o1)$, $[20] = (\o0\o1\o0)(\o1)(\o0\o0)$, and
  $[27] = (\o1\o1\o0)(\o1)(\o1)$. Similarly, we redefine $\ter{n}$ to
  the prefix $\CH$-parsing of the base-3 representation of $n$, with
  digits $\oa=0$, $\ob=1$ and $\ob=2$, with each term treated as a
  separate macro-symbol.
  
  The rules of $G'$ are then defined as follows.
  First, we consider each word of $G$ of
  the form $\delta \oR$, where $\delta$ is a byte. We apply
  lazy derivation in $G$ to this (partial) word until we obtain a word
  $\sigma' \oR$ where $\sigma$ is in $\Sigma^+$ (a bit-free string
  of trits). Let $\sigma'_1\sigma'_2\cdots\sigma'_s\beta$ be the 
  prefix $\CT$-parsing of $\sigma'$. We then
  add the production $(\delta)\oR \to (\sigma'_1)(\sigma'_2) \cdots
  (\sigma'_s)(\beta)\oR$ to the rule set of $G'$, except that the
  macro-symbol $(\beta)$ is omitted if $\beta$ is empty. 
  Note that $s$ may be zero in either case.
  
  Next, we consider all strings of the form $\delta\sigma$ where
  $\delta$ is a byte (in $\Delta'$) and $\sigma$ is a tryte (in
  $\Sigma'$). Again we use lazy evaluation in $G$ to transform that
  string into a string $\sigma'\delta'$ where $\sigma'$ is a string of
  trits of $G$ and $\delta'$ is a string of bits of $G$ (which are both non-empty, by the rules of $G$).
  Let $\alpha \delta'_1\delta'_2\cdots\delta'_r$ be the suffix $\CB$-parsing of $\delta'$,
  and $\sigma'_1\sigma'_2\cdots\sigma'_s\beta$ be the prefix $\CT$-parsing of $\sigma'$. We then add to
  the rules of $G'$ the production
    \[
      (\delta)(\sigma) \to (\sigma'_1)(\sigma'_2)\cdots(\sigma'_s)(\beta)(\alpha)(\delta'_1)(\delta'_2)\cdots(\delta'_r)
    \]
  except that $(\alpha)$ is omitted if $\alpha$ is empty, and $(\beta)$ is omitted if $\beta$ is empty.
  
  Finally, we consider every string of the form $\oL \sigma$ where
  $\sigma$ is one of the trytes of $\Sigma'$, and use greedy
  derivation of $G$ to turn it into a string $\oL \delta'$ where
  $\delta$ is a trit-free string of bits. Let $\alpha\delta'_1\delta'_2 \cdots\delta'_r$
  be the suffix $\CB$-parsing of $\delta'$. We add to the rule sof $G'$
  the production $\oL (\sigma) \to \oL (\alpha)(\delta'_1)(\delta'_2)\cdots(\delta'_r)$,
  omitting $(\alpha)$ if $\alpha$ is empty.\footnote{This is not good, rethink.  For the 
  fixed-length case we should get alternating trytes and bytes.}
  
  This construction becomes quite a bit simpler when we use
  fixed-length codes $\CB = \Delta^k$ and $\CT=\Sigma^k$ with $k\geq 2$. In that case, the lazy
  derivation of any string $\delta \oR$ for $\delta\in \Delta'$
  generates a string $\gamma\oR$ where $\gamma$ has at most $k$
  trits of $G$, and is therefore a single tryte. The lazy derivation of any string $\delta
  \sigma$, where $\delta$ is a byte and $\sigma$ is a tryte,
  generates a string $\sigma'\delta'$ where $\delta'$ is
  always a single byte, and $\sigma'$ is a single tryte. 
  Finally, the lazy derivation of $\oL \sigma$, where $\sigma$ is a
  single tryte of $G$, can be adjusted to generate `$\oL$',  $\oL\delta'$,
  or $\oL \sigma'\delta'$ where $\delta'$ is a single byte and $\delta'$ a single tryte
  that is lexicographically smaller than $\sigma$.  Thus we can restrict the 
  set of bytes to the code words $\CB$ (excluding its proper
  suffixes).\footnote{See \texttt{temp.tex} for further stuff.}
  
\begin{thebibliography}{99}

\bibitem{KNU} Placeholder.

\end{thebibliography}

\end{document}
