%%%%%%%% 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}