%%%%%%%% Versuch Poster IMA Minneapolis April 2007
%%%%%%% letzte Version: 26.3.2007
%\documentclass[draft]{a0poster}
\documentclass[envcountsame,portrait]{a0poster}
\usepackage[absolute]{textpos}
\usepackage{graphics,wrapfig,times}
%\usepackage{gregtalk}
%\usepackage{llncs}
% These colours are tried and tested for titles and headers. Don't
% over use color!
\usepackage{color}
\definecolor{DarkBlue}{rgb}{0.1,0.1,0.5}
\definecolor{Red}{rgb}{0.9,0.0,0.1}
%%%%%%%%%%%%% gregtalk.sty
\usepackage{colordvi}
\usepackage{graphics}
%\usepackage{amsmath, amssymb, amsthm, amscd}
%\usepackage{pstricks,pst-text}
\newcommand{\MyBlue}[1] {\Color{ 0.7 0.7 0 0.3}{#1}}
\newcommand{\MyRed}[1] {\Color{ 0 0.5 0.3 0.2}{#1}}
%%%%%%%%% dunkleres Gruen
\newcommand{\MyGreendunkel}[1] {\Color{ 0.5 0.2 0.8 0.3}{#1}}
%%%%%%%%%
%%%%%%% helleres Gruen
\newcommand{\MyGreenhell}[1] {\Color{ 0.6 0.2 1.0 0.0}{#1}}
%%%%%%%%
%%%%%%% Versuchs-Gruen
\newcommand{\MyGreenmittel}[1] {\Color{ 0.6 0.2 1.0 0.15}{#1}}
%%%%%%%%
\newcommand{\MyOrange}[1] {\Color{ 0 0.5 1.0 0.0}{#1}}
\newcommand{\MyYellow}[1]{\Color{ 0.0 0.4 1.0 0.1}{#1}}
%%% von mir definiert:
\newcommand{\MyPink}[1] {\Color{ 0.35 0.6 0.15 0.25}{#1}}
%%%
\newcommand{\und}[1]{{\Red{\underline{\Black {#1}}}}}
\newcommand{\explain}[1]{\MyBlue{#1}}
\newcommand{\new}[1]{\MyOrange{#1}}
\newcommand{\defeq}{\stackrel{\scriptstyle\mathrm{def}}{=}}
\newcommand{\punct}[1] {\hspace{0.3cm}\text{#1}}
\newcommand{\redemph}[1]{\MyRed{\underline{\Black{\em #1}}}}
\newcommand{\redund}[1]{\MyRed{\underline{\Black{#1}}}}
\newcommand{\mathemph}[1] {\MyOrange{#1}}
\newcommand{\nomathemph}[1]{\Black{#1}}
\newcommand{\constemph}[1]{\MyYellow{#1}}
\newcommand{\refemph}[1]{\MyBlue{#1}}
\newcommand{\vf}[1]{\ \\ \vspace{\stretch{#1}}}
%%%%%%%%%%%%%%%%%%%%%% Gregtalk.sty ENDE
%%%%%%%%%%%%%%%%%%%%%% Farben aus Gregtalk.sty
\newcommand{\tb}[1]{\textcolor{blue}{#1}}
\newcommand{\tr}[1]{\textcolor{red}{#1}}
\newcommand{\tg}[1]{\textcolor{green}{#1}}
%\newcommand{\tg}[1]{\MyGreenhell{#1}}
%\newcommand{\tg}[1]{\MyGreenmittel{#1}}
%\newcommand{\tg}[1]{\MyGreendunkel{#1}}
\newcommand{\tor}[1]{\MyOrange{#1}}
%%%%%%%%%%%%%% Macros aus Arbeit mit Martin
\usepackage{times}
%\usepackage{mathptm}
\usepackage{eucal}
\usepackage{a4}
\usepackage{cite}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{xspace}
%\usepackage[mathb]{mathabx}\changenotsign
\DeclareFontFamily{U}{mathb}{\hyphenchar\font45}
\DeclareFontShape{U}{mathb}{m}{n}{
<5> <6> <7> <8> <9> <10> gen * mathb
<10.95> mathb10 <12> <14.4> <17.28> <20.74> <24.88> mathb12
}{}
\DeclareSymbolFont{mathb}{U}{mathb}{m}{n}
\DeclareMathSymbol{\precneq}{3}{mathb}{"AC}
\newcounter{theorem}
\newcounter{example}
\newcommand{\reduceq}{\preceq}
\newcommand{\reducneq}{\precneq}
\newcommand{\notreduceq}{\npreceq}
%\DeclareMathSymbol{\Freeprod}{1}{mathb}{"06}
\DeclareMathOperator*{\Freeprod}{\raisebox{-1.4ex}[1ex][0ex]{\text{\huge*}}}
\newcommand{\freeprod}{*}
\newcommand{\range}{\operatorname{range}}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\SL}{\operatorname{SL}}
\newcommand{\IR}{\mathbb{R}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\IC}{\mathbb{C}}
\newcommand{\IA}{\mathbb{A}}
\newcommand{\IB}{\mathbb{B}}
\newcommand{\IQ}{\mathbb{Q}}
\newcommand{\IF}{\mathbb{F}}
\newcommand{\IZ}{\mathbb{Z}}
\newcommand{\IH}{\mathbb{H}}
\newcommand{\IK}{\mathbb{K}}
\newcommand{\IN}{\mathbb{N}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\IM}{\mathbb{M}}
\newcommand{\IP}{\mathbb{P}}
\newcommand{\IS}{\mathbb{S}}
\newcommand{\IT}{\mathbb{T}}
\newcommand{\IO}{\mathbb{O}}
\newcommand{\IX}{\mathbb{X}}
\newcommand{\IY}{\mathbb{Y}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calH}{\mathcal{H}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\NP}{\mathcal{NP}}
\newcommand{\person}[1]{\textsc{#1}}
\newcommand{\aname}[1]{\textsf{#1}}
\newcommand{\BSS}{{BSS}\xspace}
\newcommand{\BCSS}{{BSS}\xspace}
\newcommand{\SAG}{algebraically generated\xspace}
\newcommand{\SAE}{algebraically enumerated\xspace}
\newcommand{\SAP}{algebraically presented\xspace}
\newcommand{\SAEP}{algebraically enumerated\slash presented\xspace}
\newcommand{\SAGEP}{algebraically generated\slash enumerated\slash presented\xspace}
\newcommand{\mycite}[2]{\cite[\textsc{#1}]{#2}}
\newcommand{\COMMENTED}[1]{}
\newcommand{\comment}[1]{\marginpar{\footnotesize\sf #1}}
\newtheorem{observation}[theorem]{Observation}{\bfseries}{\itshape}
\newtheorem{theorem}[theorem]{Theorem}{\bfseries}{\itshape}
\newtheorem{deff}[theorem]{Definition}{\bfseries}{\itshape}
\newtheorem{scholiumf}[theorem]{Scholium\footnotemark}
\newtheorem{myclaim}[theorem]{Claim}{\bfseries}{\itshape}
\newtheorem{myquestion}{Question}{\bfseries}{\itshape}
\newcommand{\ri}{\IR^{\infty}}
\newcommand{\nor}{\text{\rm n}} %generated normal subgroup
\newtheorem{example}[example]{Example}{\bfseries}{\itshape}
%%%%%%%%%%%%%%%%%
% see documentation for a0poster class for the size options here
\let\Textsize\normalsize
\def\Head#1{\noindent\hbox to \hsize{\hfil{\LARGE\color{DarkBlue} #1}}\bigskip}
\def\LHead#1{{\Large \tg{#1}}\smallskip}
\def\Subhead#1{\noindent{\large\color{DarkBlue} #1}}
\def\Title#1{\noindent{\Huge\color{DarkBlue} \centerline{#1}}}
% Set up the grid
%
% Note that [40mm,40mm] is the margin round the edge of the page --
% it is _not_ the grid size. That is always defined as
% PAGE_WIDTH/HGRID and PAGE_HEIGHT/VGRID. In this case we use
% 15 x 25. This gives us a wide central column for text (7 grid
% spacings) and two narrow columns (3 each) at each side for
% pictures, separated by 1 grid spacing.
%
% Note however that texblocks can be positioned fractionally as well,
% so really any convenient grid size can be used.
%
\TPGrid[40mm,40mm]{15}{25} % 3 - 1 - 7 - 1 - 3 Columns
% Mess with these as you like
\parindent=0pt
%\parindent=1cm
\parskip=0.5\baselineskip
% abbreviations
\newcommand{\ddd}{\,\mathrm{d}}
\begin{document}
\begin{textblock}{17}(-1.1,0)
\baselineskip=3\baselineskip \Title{The word problem for a
class of groups with infinite presentation:}
\Title{A computationally
universal problem in the BSS model}
\end{textblock}
\begin{textblock}{17}(-1.1,1.5)
\centerline{\Large \tg{Klaus Meer, University of Southern Denmark, Odense}}
\end{textblock}
\begin{textblock}{17}(-1.1,2.0)
\centerline{\Large joint work with Martin Ziegler, Paderborn}
\end{textblock}
\begin{textblock}{17}(-1.1,2.5)
\Large \centerline{\tr{IMA Minneapolis, April 2007}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% SEITE 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\normalsize
\begin{textblock}{4.7}(-0.1,4.0)
\centerline{\tb{Abstract}}
The word problem for discrete groups is well-known to be undecidable
by a Turing Machine; more precisely, it is reducible both to and from
and thus equivalent to the discrete Halting Problem.\\
The present work introduces and studies
a real extension of the word problem
for a certain class of groups
which are presented as quotient groups of a free group and a
normal subgroup. Most important, these groups may be
generated by \tr{uncountably} many generators
with index running over certain sets of real numbers.
This includes many mathematically important groups which
are \tb{not captured} by the finite framework of the classical word problem.\\
Our contribution extends computational group theory from the
discrete to the Blum-Shub-Smale (\BSS) model of real number computations.
We believe this to be an interesting step towards
applying \BSS theory, in addition to semi-algebraic geometry,
also to further areas of mathematics.\\
The main result establishes the word problem for such groups to be
computationally
equivalent to the Halting Problem for BSS machines.
It thus provides the first non-trivial example of a
natural problem \tr{complete}, that is, computationally universal
for this model.
\end{textblock}
\begin{textblock}{4.7}(-0.1,9.5)
\centerline{-1-}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% ENDE SEITE 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% Senkrecht S.2
%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(-0.1,10)
\centerline{\tb{1. Introduction}}
In 1936, \person{Alan M. Turing} introduced the now so-called
Turing Machine and proved the associated Halting Problem $H$,
that is the question of termination of a given such machine $M$,
to be undecidable. On the other hand
simulating a machine $M$ on a Universal Turing Machine
establishes $H$ to be semi-decidable.
In the sequel, several other problems $P$ were also revealed
semi-, yet un-decidable. Two of them,
\tr{Hilbert's Tenth} and the \tr{Word Problem} for groups,
became particularly famous, not least because they arise and
are stated in purely mathematical terms whose relation to
computer science turned out considerable a surprise.
For real number problems of Scientific Computation as for
example in Numerics, Computer Algebra, and Computational Geometry
on the other hand,
several independent previous formalizations were in 1989 subsumed
in a real counterpart to the classical Turing Machines
called the Blum-Shub-Smale, for short \BSS model.
\end{textblock}
\begin{textblock}{4.7}(-0.1,14.5)
\centerline{-2-}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 2 SENKRECHT
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 3 SENKRECHT
%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(-0.1,15)
It bears many structural similarities
to the discrete setting like for example the existence
of a Universal Machine
or the undecidability of the
associated \tr{real Halting Problem $\IH$}, that is the
question of termination of a given \BSS-machine $\IM$.
Concerning \BSS-complete problems $\IP$ however, not many are known
so far. The Tu\-ring-complete ones for example and, more generally,
any discrete problem becomes decidable over the reals;
and \emph{extending} an undecidable
discrete problem to the reals generally does not work either:
\tg{Example 1.}
Hilbert's Tenth Problem (over $R$) is the task of deciding,
given a multivariate polynomial equation over $R$,
whether it has a solution in $R$.
For integers $R=\IZ$, this problem was
proven \tg{(Turing-)undecidable}.
For reals $R=\IR$ however, it \emph{is}
\tg{(\BCSS-)decidable} by virtue of
Tarski's Quantifier Elimination.
\medskip
The goal of this work is to extend the classical word problem
for finitely presented groups to a new class of groups and show its
computational equivalence to the real Halting Problem $\IH$.
\end{textblock}
\begin{textblock}{4.7}(-0.1,19.5)
\centerline{-3-}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%
%%%% ENDE SEITE 3
%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 4
%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(-0.1,20)
\centerline{\tb{2. The Word Problem: Classical and new setting}}
{\bf Definition 1.}
%\begin{theorem}\label{d:Groups0}
\begin{enumerate}
\item[a)]
The \emph{free group} $\langle X\rangle$ \emph{generated by a set} $X$,
is the set
of all finite sequences
$\bar w=x_1^{\epsilon_1}\cdots x_n^{\epsilon_n}$ with $n\in\IN$,
$x_i\in X$, $\epsilon_i\in\{-1,+1\}$, equipped with
concatenation $\circ$ as group operation subject
to the rules
\[ x\circ x^{-1}\quad=\quad1\quad=\quad x^{-1}\circ x \qquad \forall x\in X ,
\]
where $x^1:=x$ and where $1$ denotes the empty word (unit element).
\item[b)]
For a group $H$ and $W\subseteq H$, $\langle W\rangle_{H}$ is
the subgroup of $H$ generated by $W$
and $\langle W\rangle_{H\!\nor}$ the normal subgroup of $H$ generated by $W.$
\item[c)]
For $X$ and $R\subseteq\langle X\rangle$
consider the quotient group $G:=\langle X\rangle/\langle R\rangle_{\nor}$,
also denoted by $\langle X|R\rangle$.
If both $X$ and $R$ are finite, the tuple $(X,R)$
will be called a \tr{finite presentation} of $G$;
if $X$ is finite and $R$ recursively enumerable (by a Turing machine,
that is in the discrete sense; equivalently: semi-decidable),
it is a \tr{recursive presentation};
if $X$ is finite and $R$ arbitrary,
$G$ is \tr{finitely generated}.
\end{enumerate}
%\end{theorem}
\end{textblock}
\begin{textblock}{4.7}(-0.1,24.5)
\centerline{-4-}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%
%%%% ENDE SEITE 4
%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(5,4)
{\bf Definition 2.} (Word Problem)
The \tr{word problem} for $\langle X|R\rangle$ is
the task of deciding, given $\bar w\in\langle X\rangle$,
whether $\bar w=1$ holds in $\langle X|R\rangle$.
\smallskip
The famous work
of Novikov and, independently, Boone
establishes the word problem for finitely presented
groups to be Turing-complete:
{\bf Theorem 1.} (\tb{Novikov}, \tb{Boone}, 1958/59)
There exists a finitely presented
group $\langle X|R\rangle$ whose associated word problem
is many-one reducible by a Turing machine
from the discrete Halting Problem $H$.
\smallskip
An important tool in the proof is
{\bf Theorem 2.} (\tb{Higman Embedding Theorem})
Every recursively presented group
can be embedded in a finitely generated one.
\smallskip
The above embedding theorem gives a reduction from the
word problem of recursively presented groups to that of
finitely generated ones.
\smallskip
Note here that trivially each such embedding is computable
by a Turing machine.
Computability (in the BSS model) of embeddings
will not any longer be a triviality for the groups
we consider below!
\end{textblock}
\begin{textblock}{4.7}(5,9.5)
\vfill{\centerline{-5-}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(5,10)
{\bf Definition 3.} (Real Groups and their Word Problem)
Let $X\subseteq\ri := \bigoplus_{d \in \IN} \IR^d $ and
$R\subseteq\langle X\rangle\subseteq \ri$.
The tuple $(X,R)$ is called a \tr{presentation}
of the \tr{real group} $G=\langle X|R\rangle$.
This presentation is \tr{\SAG} if $X$
is \BSS-decidable and $X\subseteq\IR^N$ for some $N\in\IN$.
$G$ is termed \tr{\SAE}
if $R$ is in addition \BSS semi-decidable;
if $R$ is even \BSS-decidable,
call $G$ \tr{\SAP.}
The \tr{word problem} for the presented real group
$G=\langle X|R\rangle$ is
the task of \BSS-deciding, given $\bar w\in\langle X\rangle$,
whether $\bar w=1$ holds in $G$.
Correspondence between
classical discrete and new real notions:
\begin{center}
\begin{tabular}{l@{\;\;}|@{\;\;}l}
\hspace*{\fill} Turing\hspace*{\fill} & \hspace*{\fill} \BCSS\hspace*{\fill}
\\ \hline
finitely generated & \SAG \\
recursively presented & \SAE \\
finitely presented & \SAP
\end{tabular}
\end{center}
The next example shows already one major difference to finitely presented groups:
Decidability of the word problem might depend on the representation.
\end{textblock}
\begin{textblock}{4.7}(5,14.5)
\vfill{\centerline{-6-}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(5,15)
\tg{Example 2.} Three presentations $\langle X|R\rangle$ of $(\IQ,+)$:
\begin{enumerate}
\itemsep2pt
\item[a)]
$\displaystyle X\;=\;\big\{ x_r : r\in\IQ \big\}$,
\quad $\displaystyle R\;=\;\big\{ x_r x_s=x_{r+s}: r,s\in\IQ\big\}$.
\item[b)]
$\displaystyle X\;=\;\{ x_{p,q} : p,q\in\IZ, q\not=0\}$,\\
$\displaystyle R\;=\;\big\{ x_{p,q} x_{a,b}=x_{(pb+aq,qb)}:
p,q,a,b\in\IZ\big\}\;\cup\; \\
\hspace*{2.3cm} \big\{
x_{p,q}=x_{(np,nq)}:p,q,n\in\IZ, n\not=0\big\}$.%
\item[c)]
Let $(b_i)_{i\in I}$ denote an algebraic basis
of the $\IQ$--vector space $\IR$; w.l.o.g. $0\in I$ and $b_0=1$.
Consider the linear projection $P:\IR\to\IQ$,
$\sum_i r_i b_i\mapsto r_0$ with $r_i\in\IQ;\\
X\;=\; \big\{ x_t:t\in\IR \big\} \\
R\;=\; \big\{ x_t x_s=x_{t+s}:t,s\in\IR\big\}
\;\cup\;\big\{ x_t=x_{P(t)}:t\in\IR\big\} \enspace . $
\end{enumerate}
Case~b) yields an algebraic presentation,
a) is not even \SAG but c) is.
The word problem is decidable for a) and b) but not for c).
\smallskip
\tg{Example 3.} Weil representation of $SL_2(\R)$
\end{textblock}
\begin{textblock}{4.7}(5,19.5)
\vfill{\centerline{-7-}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(5,20)
\centerline{\tb{Main Results}}
{\bf Theorem 3.} Let $G=\langle X|R\rangle$ denote an \SAE real group.
Then the associated word problem is \BSS semi-decidable.
{\bf Proof idea:} Quantifier elimination for real closed fields.
\smallskip
\tr{Main Theorem}. %(M. \& Ziegler)
There exists an \SAP real group $\calH=\langle X|R\rangle$
such that $\IH$ is \BSS-reducible to the word problem
in $\calH$.
{\bf Sketch of proof ideas:}
\begin{itemize}
\item[-] generalization of group theoretic tools to our setting:
effective homomorphisms, amalgamation, HNN extensions
\item[-] introduce effectively benign (e.b.) groups; description of each
path set as e.b. subgroup of an \SAP group.
Notion allows reduction of word problem between certain real groups
\item[-] joining path sets by exploiting properties of e.b. groups
gives computable embedding in free \SAP group.
\end{itemize}
\end{textblock}
\begin{textblock}{4.7}(5,24.5)
\vfill{\centerline{-8-}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 9
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(10.1,4)
\centerline{\tb{A few proof details}}
{\bf Definition 4.} (HNN extensions)
Let $G=\langle X|R\rangle$, let $A=\langle V|R\rangle,B=\langle W|R\rangle$
be subgroups of $G$, and
$\phi': \langle V \rangle \to \langle W \rangle$ be
a realization of an isomorphism $\phi$ between $A$ and $B$. The
\tr{Higman-Neumann-Neumann (HNN)} extension
of $G$ relative to $A,B$ and $\phi$ is the presented group
\[\langle G;t\;|\; ta=\phi(a)t\forall a\in A\rangle :=
\big\langle X\cup\{t\}\;|\;R\,\cup\,
\{\phi'(\bar v)t\bar v^{-1}t^{-1}:\bar v\in V\}\big\rangle
,\]
%$G$ is the \emph{base} of the HNN extension,
where $t\not\in X$ is a new generator called the \emph{stable letter}.\\
Note: $A=B$ possible in above definition.
%, and
%$A$ and $B$ are the \emph{associated subgroups} of the extension.
{\bf Definition 5.} (Effectively benign groups)
Let $X\subseteq\ri$, $V\subseteq\langle X\rangle$.
%\comment{Im Hinblick auf Lemma~\ref{l:Benign}a)
%ausdr\"{u}cklich NICHT fordern, $G$ m\"{u}sse SAG sei!}
The subgroup $A=\langle V|R\rangle$ of
$G=\langle X|R\rangle$ is \tr{effectively benign (e.b.)
in $G$} if the HNN extension
$\langle X;t\,|\, ta=at\forall a\in A\rangle$
admits an effective embedding
into some \SAP group $K=\langle Y|S\rangle$.
\tr{Important}: If $A$ is e.b. in $G$, then $A$'s word problem is reducible to $K$'s.
{\bf Lemma 1.} (Properties of e.b. groups)\\
a)\
Let $A=\langle V|R\rangle\subseteq H=\langle W|R\rangle\subseteq G=\langle X|R\rangle$
sub-/groups,
$V\subseteq\langle W\rangle, W\subseteq\langle X\rangle$.
If $W$ is decidable and $A$ e.b. in $G$,
then $A$ is e.b. in $H$.\\
b)\
If $G=\langle X|R\rangle$ is \SAP
and subgroup $A=\langle V|R\rangle$
has decidable $V$,
then $A$ is e.b. in $G$.
\end{textblock}
\begin{textblock}{4.7}(10.1,9.5)
\vfill{\centerline{-9-}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 9
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 10
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(10.1,10)
c)\
If $A$ is e.b. in $G$
and $\phi:G\to H$ an effective embedding,
then $\phi(A)$ is e.b. in $\phi(G)$.\\
%\item[d)]
% Let $A$ and $B$
% be effectively benign in \SAP $G$.
% Then $A\cap B$ admits a presentation
%\item[e)]
% Let $A$, $B$, $G$ as in d);
% then $\langle A\cup B\rangle_G$ admits a
% presentation\footnote{possibly different from
% \label{f:Union} $\langle V\cup W|R\rangle$}
% effectively benign in $G$.
d)\
Let $(A_i)_{i\in I}$ be uniformly e.b.
in $G$, then
$\langle\bigcup_{i\in I} A_i\rangle$ admits a
presentation e.b. in $G$.
\centerline{\tb{Path sets and e.b. groups}}
Consider
$\IH\subseteq\ri$ real halting problem,
$\IM$ \BCSS machine semi-deciding $\IH$,
$\gamma$ computation path
with path set $\IA_{\gamma}\subseteq\IR^{d},$
$\IB_\gamma\subseteq\IR^D$
set of intermediate results
for computation along $\gamma
(d,D \in \IN$ only depend on $\gamma$).
\tb{Goal:} Use Lemma 1 to express $\IA_{\gamma}$ as a group
$U_{\gamma}$ e.b. in an algebraically presented group $G$ to be defined.
{\bf Theorem 5.}
Let $ X := \{x_{(i,s)}:s\in\IR,i\in\IN\}\cup\{y\},
G := \langle X\rangle $
and subgroup
$ U_\gamma := \langle\bar w_{\bar r}:\bar r\in\IA_\gamma\rangle$
where
$\bar w_{(r_1,\ldots,r_d)}:=x^{-1}_{(k,r_d)}\cdots x^{-1}_{(1,r_1)}\cdot y
\cdot x^{}_{(1,r_1)}\cdots x^{}_{(k,r_d)}$
\ for $r_1,\ldots,r_d\in\IR$.
Then $U_\gamma$ has a presentation which is effectively benign in the
\SAP group $G.$
\end{textblock}
\begin{textblock}{4.7}(10.1,14.5)
\vfill{\centerline{-10-}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 10
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 11
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(10.1,15)
To prove Theorem 5 one assigns to each operation $\sigma$
along path $\gamma$ a suitable group $L_{\sigma}.$ The latter
is a subgroup of a HNN extension $C$ of $G.$ The definition
of $C$ below guarantees $L_{\sigma}$ to be e.b. in $G.$
{\bf Definition 6.}
Let $C$ denote the infinite HNN extension
\begin{multline*}\bigg\langle G \;\;;\;\;
\begin{array}{lr}
a_{(i,t)}&\forall t\in\IR\;\forall i\in\IN \\
m_{(i,t)}&\forall 0\not=t\in\IR\;\forall i\in\IN
\end{array}
\bigg| \\
\begin{array}{r@{\:=\:}lr}
a_{(i,t)}\cdot g&\,\phi_{(i,t)}(g)\cdot a_{(i,t)}&
\forall g\in G \;\forall (i,t) \\
m_{(i,t)}\cdot g&\psi_{(i,t)}(g)\cdot m_{(i,t)}&
\forall g\in G \;\forall (i,t) \\
\end{array}
\bigg\rangle \end{multline*}
%with base $G$ and stable letters $a_{(i,t)}$, $m_{(i,t)}$ as above.
Here, $\phi_{(i,t)},\psi_{(i,t)}:G\to G$ denote the
isomorphisms
\[ \begin{array}{rlll}
\phi_{(i,t)}:&x_{(i,s)}\mapsto x_{(i,s+t)}, \;\;
& x_{(j,s)}\mapsto x_{(j,s)}, & \;\; y\mapsto y \\[0.8ex]
\psi_{(i,t)}:&x_{(i,s)}\mapsto x_{(i,s\cdot t)}, \;\;
& x_{(j,s)}\mapsto x_{(j,s)}, & \;\; y\mapsto y
\end{array} \;\quad \forall s\in\IR\;\;.
\]
\end{textblock}
\begin{textblock}{4.7}(10.1,19.5)
\vfill{\centerline{-11-}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 11
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% SEITE 12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{textblock}{4.7}(10.1,20)
Note: Commuting a stable letter $a_{(i,t)}$ `causes'
a real addition in the sense that
$a_{\scriptscriptstyle(i,t)}^{}\cdot x_{(i,s)}\cdot
a_{\scriptscriptstyle(i,t)}^{-1}=x_{(i,s+t)}$.
Furthermore:\\
\[a_{\scriptscriptstyle(i,t)}^{}\cdot\bar w_{(r_1,\ldots,r_i,\ldots,r_D)}
\cdot a_{\scriptscriptstyle(i,t)}^{-1}
\quad=\quad\bar w_{(r_1,\ldots,r_i+t,\ldots,r_D)}.\]
Similarly with generators $m_{(i,t)}$ for multiplication.
Now obtain efficiently benignness of $U_{\gamma}$ from
that of all the $L_{\sigma}$'s along Lemma 1.
Finally, combine all the path groups $U_{\gamma}$ by a similar
technique to obtain the Main Theorem.
\vspace{1.5cm}
{\bf Reference.} K. Meer, M. Ziegler: Real Computational Universality: The
Word Problem for a class of groups with infinite presentation. Preprint 2006.
If interested send email to: meer@imada.sdu.dk
\end{textblock}
\begin{textblock}{4.7}(10.1,24.5)
\vfill{\centerline{-12-}}
\end{textblock}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% ENDE SEITE 12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}