\begin{document} %\maketitle %\frontmatter \thispagestyle{empty} %\pagecolor{bgblue} \begin{minipage}{0.25\textwidth} \includegraphics[width=0.9\textwidth]{komlogo} \end{minipage} \begin{minipage}{0.69\textwidth} \begin{center} \sc Department of Computer Science \\ Faculty of Mathematics, Phisics and Informatics \\ Comenius University, Bratislava \end{center} \end{minipage} \vfill \begin{center} \begin{minipage}{0.8\textwidth} \hrule \bigskip\bigskip \centerline{\LARGE\sc The Tape--size and} \medskip \centerline{\LARGE\sc Extended Chomsky hierarchy} \smallskip %\centerline{\huge\sc Arch� Elektronickch Dokumentov} \centerline{(master thesis)} \bigskip \bigskip \centerline{\large\sc \v Lubo\v s Steskal} \bigskip\bigskip \hrule \end{minipage} \end{center} \vfill {\bf Advisor:}\\ Prof. RNDr. Branislav Rovan, PhD. \hfill Bratislava, 2006 \eject % EOP i %ABSTRAKT NA SVOC \tableofcontents \begin{chapter}{Introduction} The theory of recursive functions and effective computability is a scientific field with many interesting results; some of them might have philosophical impact. It is well known that there are problems, which cannot be solved by algorithms. In fact, a whole hierarchy of unsolvable problems opens before us, if we go a little bit deeper in our studies. There are many results that give us better understanding of both formal languages of logic and of computer science \cite{Rog92}. Although, there are more approaches to study this subject, oracle machines surely provide a good computational model to deal with. In the recent years (but also sooner in the past) a few new computational models differing standard framework were proposed. These models shared the attribute of being stronger then the Turing Machine. Some of them were purely theoretical concepts, some tried to model a phenomenon that could be observed in reality \cite{cierne_diery1}. Such models are sometimes called \emph{Hypermachines}, or machines with \emph{Super Turing computational powers}. Inspired by the models of the \emph{Accelerated Turing Machine} proposed by Bertrand Russell, Ralph Blake and Hermann Weyl and the \emph{Infinite Time Turing Machine} proposed by Joel Hamkins and Andy Lewis \cite{inftime} we created a new model of our own. Our model consists of two parts. A machine capable of an infinitely long computation and another machine processing its output. By placing constrains to the first or second machine, we obtain classes of languages which form hierarchies. One such hierarchy is very similar to the one obtained by limiting the number of queries of an oracle machine \cite{bieg-phd} \cite{bieg-sup}. The other hierarchy looks more like the \emph{Chomsky hierarchy}, but it is in the $\Sigma_3$ class of the Arithmetical hierarchy. \end{chapter} \begin{chapter}{Notation and Preliminaries} In this part, we introduce a new computational model; the \emph{Display Turing Machine}\footnote{We shall use the acronym $TMD$ to avoid confusion with the Deterministic Turing Machine}. These machines will alow us to study functions witch require possibly infinite time to be computed. The model looks like a one--tape Turing Machine equipped with another tape. We shall call this additional tape the Display Tape. During its computation, the $TDM$ can use both of the tapes as standard tapes. After the computation is done, the content of the display tape shall be considered as output. If the computation does not halt after finite time, then the limit of the display tape shall be the output of the machine. %We will consisting of an Infinite Time Turing Transducer and an acceptor used on the transducers outputs. %The transducer is a Turing machine with one input/working and one output tape. %The difference between a normal Turing Transducer and an infinite one is that we allow it to work for an infinite amount of time ($\omega$ to be precise). \begin{section}{Definitions} \begin{dfn} Let $\abc$ be a finite alphabet. We denote $\abc^\ast$ the set of all finite words consisting only from letters in $\abc$. We denote $\abc^\omega$ the set of all infinite words consisting only from letters in $\abc$. We denote $\abc^\infty=\abc^\ast\cup \abc^\omega$. \end{dfn} \begin{dfn} \label{def:ittt} \emph{Infinite Time Turing Transducer} is a $5$-tuple $(\abc,\Gamma,\delta,K,q_0)$ where $\abc \subseteq\Gamma$ is the input and sketch alphabet, $B,\$$ are special symbols for a blank space and the beginning of the output tape, $\dagger \notin \Gamma$ is a special symbol that is not allowed to be in $\Gamma$, $K$ is the set of all states of the machine, $q_0\in K$ is the beginning state and {$\delta \colon{K\times \Gamma ^2}\to {K\times\{ \{\Gamma- \{B \} \} \times\{-1,0,1\}\}^2}$} such, that $\forall a_0,a_1:\delta(q,a_0,a_1)=(p,a_0',d_0,a_1',d_1) \Rightarrow (a_0'\neq \$ \land (a_1 = \$ \Rightarrow d_1 \neq -1 \land a_1' = \$)) $ is the transition function. \end{dfn} \begin{dfn} \emph{Configuration of ITTT} $T$ is an element of the set $K\times B (\Gamma - \{B\})^\ast B\times {\mathbb N} \times \$(\Gamma - \{B,\$ \})^\ast B\times {\mathbb N}$ \end{dfn} An example for a configuration is $(p,BwB,5,\$vB,2)$. Here $p$ denotes the current state of the machine, $w$ is the word written on the auxiliary tape, $5$ means, that the head on the sketch tape is on the fifth square, $v$ is the word written on the output tape, $2$ stands for the position of the head on the output tape. T makes a computational step if it comes from one configuration to another by one application of the transition function. \begin{dfn} \emph{Computational step of ITTT} $T$ is a relation $\vdash_T$ defined over configurations of ITTT such, that $(p, Bu_0u_1\dots u_nB, k, \$v_0v_1\dots v_mB,l)\vdash_T (q,Bu_0u_1\dots u_{k-1} a u_{k+1}\dots u_nB,k+d_0, \$v_0v_1\dots v_{l-1} b v_{l+1} \dots v_mB, l+d_1) \iff \delta(p,u_k,v_l)= (q,a,d_0,b,d_1)$. We omit the index $T$ and shall write only $\vdash$ if it is obvious what machine we are referring to. \end{dfn} The output of the $ITTT$ is defined for each square of the output tape and these are then concatenated to form the output word. Output of each square is seen as a limit of the contents of that square during computation. If the content of the square doesn't change from some time on (if it changes for only a finite number of times), then the output of it is the last written letter. On the other hand, it the content changes unbounded many times, then the output is a special symbol $\dag$ which means, that the square was scratched and there is no proper output. \begin{dfn} Let T be an $ITTT$ and $w\in \abc^\ast$. Let $O^{T(w)}=\{o^{T(w)}(n)\}_{n=0}^{\infty}$ denote the sequence contents of the output tape after $n$ steps of the transducer $T$ working on the input $w$. Let $O_i^{T(w)}=\{ o_i^{T(w)}(n)\}_{n=0}^{\infty}$ denote the sequence of letters written on the $i$-th square of the output tape after $n$ steps of the computation of $T$ with $w$ on input (where the beginning of the tape $\$$ is the minus first square). Let ${\bar o}_i^{T(w)}$ be the limit of $O_i^{T(w)}$ if it converges, $\dag$ if it does not. If there exists an $l$ such that $l=\min\{i|O_i$ converges to $B\}$, then we say that $$T(w) = {\bar o}_0^{T(w)}{\bar o}_1^{T(w)}\dots{\bar o}_{l-1}^{T(w)}$$ %\in (\Gamma\cup \{\dag\})^l$ \emph{is the output the ITTT} $T$ with $w$ on input. If there is no such $l$ then \emph{the output of the ITTT} $T$ with $w$ on input is the infinite word $$T(w) = {\bar o}_0^{T(w)}{\bar o}_1^{T(w)}{\bar o}_{2}^{T(w)}\dots$$ \end{dfn} We shall now define a few useful functions and notations. \begin{nota} We denote $\C{T}_{f(n)}$ the class of all $ITTT$ for which the size of their output on $w$ of length $n$ is not bigger then $f(n)$. \end{nota} \begin{dfn} Let $T$ be an $ITTT$ with $w$ on input. $\#_{T}^\dag(w)$ shall denote the number of $\dag$ symbols in $T(w)$. \end{dfn} \begin{dfn} Let $T$ be an $ITTT$ with $w$ on input. $PAR_T(w)$ shall denote a predicate that is true if the number of non--$\dag$ symbols in $T(w)$ is even. \end{dfn} We now define the Coupled transducer machine. It is a computation model consisting of two main parts. The $ITTT$ and a machine processing its output. If the processing machine accepts the output of the transducer, then the whole model accepts the input of the transducer. The accepting machine (we might also call it acceptor) is understood as a set, and we are asking if the output is from this set. This can be understood as modeling a difficult (possibly infinite) process, which we cannot intervene once it started, but can measure and utilize its output. The accuracy of our measurements can be bounded, if $T$ is in $\C{T}_{f(n)}$. By placing some restrictions to the accepting set, we can put constrains to the accepting machine. If for example the accepting set must be regular, then we can see the accepting machine as a finite automaton accepting this set. \begin{dfn} The \emph{Coupled transducer machine} is a pair $A=(T,S)$ such, that $T$ is an ITTT and $S$ is a set. We shall call $S$ the \emph{accepting set of} $A$ and denote it $Acc(A)$. \end{dfn} \begin{dfn} Let $A=(T,Acc(A))$ be a Coupled transducer machine. We define $L(A)=\{w\in\abc^\ast| A(w)\in Acc(A)\}$. $L(A)$ is the language accepted by $A$. \end{dfn} We shall now define a (partial) function alternative to the Coupled transducer machine. \begin{dfn} Let $T$ be an $ITTT$ with $\Gamma_1$ as its working alphabet and $f$ a (partial) function $f\colon (\Gamma_1\cup\{\dag\})^\infty\to \Gamma_2^\infty$. We will call the pair $(T,f)$ a \emph{Coupled transducer function}. \end{dfn} We now define the notation of classes of machines with same boundary conditions on their transducers and acceptors. \begin{dfn} \emph{Bounded Coupled transducer machines}: \begin{itemize} \item Let $\ITTM{f(n)}{\cal L}$ denote a class of languages such that $L\in \ITTM{f(n)}{\cal L}$ if there exists an $A=(T,S)$ such that $\forall w\in \abc^\ast: (|w|=n\Rightarrow |T(w)|\leq f(n))$ and $Acc(A)\in {\cal L} \land Acc(A)\subseteq (\Gamma^\ast \cup \Gamma^\omega)$ and $L=L(A)$. \item Let $\iTTM{f(n)}{\cal L}$ denote a class of languages such that $L\in \iTTM{f(n)}{\cal L}$ if there exists an $A=(T,S)$ such that $\forall w\in \abc^\ast: (|w|=n\Rightarrow |T(w)|\leq f(n))$ and $Acc(A)\in {\cal L}$ and $L=L(A)$. \item Let $\ITTM{O(f(n))}{\cal L}$ denote a class of languages such that $L\in \ITTM{O(f(n))}{\cal L}$ if there exists an $A=(T,S)$ such that $\forall w\in \abc^\ast: (|w|=n\Rightarrow |T(w)|\in O(f(n)))$ and $Acc(A)\in {\cal L} \land Acc(A)\subseteq (\Gamma^\ast \cup \Gamma^\omega)$ and $L=L(A)$. \item Let $\iTTM{O(f(n))}{\cal L}$ denote a class of languages such that $L\in \iTTM{O(f(n))}{\cal L}$ if there exists an $A=(T,S)$ such that $\forall w\in \abc^\ast: (|w|=n\Rightarrow |T(w)|\in O(f(n)))$ and $Acc(A)\in {\cal L}$ and $L=L(A)$. \end{itemize} \end{dfn} \begin{dfn} \emph{Bounded Coupled transducer machines}: \begin{itemize} \item Let $\ITTM{g(n)}{\cal F}$ denote a class of (partial) functions such that $F\in \ITTM{g(n)}{\cal F}$ if there exists an $A=(T,f)$ such that $\forall w\in \abc^\ast: (|w|=n\Rightarrow |T(w)|\leq g(n))$ and $f\in {\cal F}$. \item Let $\ITTM{O(g(n))}{\cal F}$ denote a class of (partial) functions such that $L\in \ITTM{O(g(n))}{\cal F}$ if there exists an $A=(T,f)$ such that $\forall w\in \abc^\ast: (|w|=n\Rightarrow |T(w)|\in O(g(n)))$ and $f\in {\cal F}$. \end{itemize} \end{dfn} \begin{nota} We denote $\C{TM}$ ($\C{TM}'$) the set of all total (partial) functions computable by common Turing transducers. \end{nota} In the text, we might sometimes refer to a machine $M$ accepting a given language $L$ belonging to one of the classes by writing that $M$ is in the respective class (e.g. $M\in \iTTM{f(n)}{\cal L}$). By this we don't mean that the code of $M$ is in the class mentioned, but we want to say, that $M$ satisfies the criteria laid on it by the respective class (e.g. if $M=(T,S)$ then the output size of $T$ is no larger then $f(n)$ and $S\in\C{L}$). We shall now define a machine equivalent to the Infinite time Turing machine with one transfinite step as presented by Hamkins and Lewis. \begin{nota} Let $\C{L}_{RE^\ast}$ be the class of languages with possibly infinitely long words, for which there exists a Deterministic Turing machine $M$ accepting them. We assume that an infinite word is accepted by a Deterministic Turing machine if the machine enters its accepting state after finite number of computational steps. \end{nota} \begin{dfn} The \emph{Infinite Time Turing machine with one transfinite step} is a Coupled transducer $A$ with $Acc(A)\in \C{L}_{RE^\ast}$. \end{dfn} \end{section} In the following text, we might omit some indexes if it their use would be obvious from the context. If $P(x)$ is a predicate, we shell denote $P$ the set of all $x$ satisfying $P(x)$. \end{chapter} \begin{chapter}{Building hierarchies in $\Sigma_3$} \begin{section}{General properties of Coupled transducer machines} We shall now show some basic properties of the Infinite time Turing transducers and Coupled transducer machines with very simple sets and small output tape. This way, one can get the intuition of what could these machines do and what are the major factors affecting their computational power. First of all, we shall show what is the power of `nice' machines, machines that cannot accept a $\dag$ symbol. \begin{lma} $\Sigma_2 \subseteq \ITTM{1}{\C{R}}$. \label{lma:1} %Let $L\in \Sigma_2 \Rightarrow \exists A\in ITTM$ with one transfinite step and $(\forall w~\in~Acc(A)): (|w|=1 \land w \in \Gamma)$ such that $L(A,Acc(A))=L$ \end{lma} \begin{proof} Let $M$ be an oracle machine\footnote{with an oracle for the halting problem of Turing machines} accepting $L$. We will construct a corresponding $CTM$ $A=(T,Acc(A))$ accepting $L$. $T$ will simulate a multi tape machine, which can change the number of its tapes during computation. This can be achieved by serially writing the contents of all simulated tapes onto the scratch tape and separate them with the $\#$ symbol. $T$ shall work the very same way as $M$ does, as long as there is no oracle query. If $M$ writes something to the oracle tape, then $T$ creates a new tape (for each query a new tape) and writes the same onto that tape. If $M$ enters the query state, the following happens: \begin{enumerate} \item{$T$ writes its current configuration at the end of a special tape. We shall call it \emph{Query Configurations Stack Tape}.} \item{$T$ writes a unique identifier (e.g. number of oracle call) at the beginning of the respective oracle tape and also at the end of the \emph{QCST}.} \item{$T$ starts a parallel simulation of the machine whose code is written on the appropriate oracle tape.} \item{$T$ parallely continues the computation of $M$ as if the oracle answer was no (i.e. as if the machine described on the oracle tape should not halt).} \end{enumerate} If the simulated oracle machine $M$ enters a halting state, $T$ will write the symbol $1$ onto the accepting square if $M$ accepts and $0$ if it does not. This way, there are numerous tapes used. There is one tape of the original machine $M$, one \emph{QCST} and $k$ oracle tapes where $k$ is the total number of oracle calls in the computation of $M$ so far. We can see, that this way, there can be many computations simulated parallely. Of course, the parallelism is only simulated by $T$. Should the simulation of a machine $Z$ written on the oracle tape $z$ halt, then $T$ must roll back its entire computation and free the tape $z$ which is no more needed. There is no problem with the rollback, for all the necessary information is stored on the \emph{QCST}. All oracle simulations, which started after the simulation of $Z$, are also to be disposed. This can also be done without any problem because their identifiers are also written on the \emph{QCST}. Finally, if the wrong simulation of $M$ already stopped and $T$ has printed an appropriate symbol on the output square, it needs to be cleared. If this happens, $T$ will change the output square to $0$. We define $Acc(A)=\{1\}$ Machine $A$ as described above is in $ITTM{1}{\C{R}}$, since is a proper $ITTT$ and $Acc(A)$ is obviously a regular set. $L\subseteq L(T,Acc(A))$:\\ $w\in L \Rightarrow w\in L(M) \Rightarrow$ there exists a finite accepting computation of $M$. This means, that there is a finite number of oracle queries. We will show, that the simulation of $M$ done by $T$ eventually follows the same computation as $M$ does. From the construction of $T$ it is obvious, that there is no problem with those parts of the computations which don't contain an oracle call. So all we have to show is that after some finite time $T$ will provide the correct answer to the each oracle query in the computation of $M$. We shall prove this by contradiction. Let $k$ denote the number of the first query in the computation of $M$ for which $T$ never generates the correct answer. There may be two reasons why this could happen. The first is, that the query was never asked. This is not possible, since for each of the queries before the $k$-th one there was a correct answer generated in a finite time. Thus the simulation had to reach the point, where the $k$-th query was asked. The second reason is that the correct answer to the query was not generated in finite time. If the machine that is the subject of this query ever halts, then the machine $T$ obtains this information after some finite number of steps (since the query simulation is parallel). So to make our assumption true, the query computation must never halt. But in this case, $T$ has the correct answer to the query immediately, since \emph{no} is the default answer to any query. This again is a contradiction. This implies, that $T$ will follow the computation of $M$ after some finite time and write the appropriate symbol onto the output square. From that moment on it will not change the content of it (for all queries that are still being simulated never halt and thus no rollback will be done). Thus the sequence of characters written on the output square converges to $1$. $L(T,Acc(A))\subseteq L$ We show, that $w\notin L \Rightarrow w\notin L(T,Acc(A))$. From the first part of the proof we already know, that $\forall k\in {\mathbb N} \exists l_k \in {\mathbb N}$ such that the first $p$ steps of $M$ are correctly simulated by $T$ in $q$ steps. Thus if the computation of $M$ halts after $k$ steps, then after $l$ steps $T$ will print $0$ onto the output square and will not change the content of it anymore. Let us consider the case, when $M$ does not stop. Then it is obvious from the construction of $T$, that after simulating exactly $l$ steps of $M$ (needing exactly $l_k$ steps of $T$) there is $0$ or $B$ written on its output square. Let $\{l_k\}_{k=1}^{\infty}; l_k\in \{0,B\}$ be the sequence of contents of the output square after $l_k$ steps. This is a subsequence of $S=\{q_i\}_{i=1}^{\infty}$ where $q_i$ is the content of the output square after $i$ steps of $T$. From that follows that if $S$ converges, then it must converge to either $B$ or $0$. Thus $w\notin L \Rightarrow w\notin L(T,Acc(A))$. \end{proof} \begin{lma} \label{lma:2} $\ITTM{1}{\C{R}}\subseteq \Sigma_2$ %Let $A$ be an ITTM such, that $\forall w\in Acc({\cal A}): |w|=1 \land w\neq \dag$, then $L({\cal A})\in\Sigma_2$. \end{lma} \begin{proof} Let $A=(T,Acc(A))$ be in $\ITTM{1}{\C{R}}$. We will construct an oracle machine $M$ (with an oracle for the halting problem of TM) accepting $w$ if and only if $w$ is in $L({ A})$. All we need to do is to determine the output of the transducer $T$ in finite time assuming, that the output belongs to $Acc({ A})$. We will utilize the fact, that $w\in Acc( A)\Rightarrow {\bar o}_0\neq\dag$ (in other words the number of changes of the output square is finite). So we will simulate $A$ and ask the oracle, whether the content of the output square will ever be changed during the forthcoming computation. If it does not, we will just check if it is in $Acc(A)$. If it does, it must happen after some finite time so we can simulate the computation to the point of the change and then ask the oracle again. This implies that $w\in L(A)\Rightarrow w\in L(M)$. On the other hand if $T(w)=\dag$ then $M$ never halts and if $T(w)\neq\dag\land T(w)\notin Acc({ A})\Rightarrow w\notin L(M)$. And so $w\notin L(A)\Rightarrow w\notin L(M)$. All we need is to show that we can ask queries as described above. The question we are asking is \emph{Given a configuration of the transducer $T$, will the content of the output change after some finite number of computational steps?} Formally let $(p,w_0,n_0,w_1,n_1)$ be a configuration of $T$. We are asking about the truth of the predicate $P\equiv \exists k \in {\mathbb N}: R(k)$, where $R(k)\equiv ((p,w_0,n_0,w_1,n_1)\vdash^k_T(q,w_0',n_0',w_1',n_1')) \land w_1 \neq w_1'$. $R(k)$ is obviously a recursive predicate $\Rightarrow P\in \Sigma_1$. Since the halting problem is $\Sigma_1$ complete we can ask the oracle our question. Thus $w\in L(A) \iff w\in L(M)$. \end{proof} \begin{thm} \label{thm:IT-S2} $\ITTM{1}{{\cal R}}=\Sigma_2$. \end{thm} \begin{proof} Is a simple corollary of lemma \ref{lma:1} and lemma \ref{lma:2}. \end{proof} We see, that the infinite computation of the Infinite time Turing transducer can be used to answer (arbitrary many, but finite) number of queries to the halting problem of common Turing machines. If we think about it for a while, we can come to the conclusion, that all that can be accepted by an output tape of size $k$, can be accepted by only one square (if all the words in the accepting set are $\dag$--free). The question is, whether we could compute more, if we could accept the words containing $\dag$-s. \begin{lma} $\Pi_2 \subseteq \iTTM{1}{{\cal R}}$ \end{lma} \begin{proof} Let $L\in \Pi_2\Rightarrow L^C \in \Sigma_2 \Rightarrow \exists M: L(M)=L^C$. We will construct an $ITTM$ $A= (T,\{\dag\})$ such that $T(w)=\dag \iff w\notin L(M)$. Let $T'$ be the transducer used in the proof of lemma 1. We already know, that $T'(w)=\dag$ if the computation of $M$ requires infinitely many oracle queries. We will create $T$ by altering $T'$ a little bit. The only reason, why $T'$ does not satisfy our needs is that if the computation of $M$ needs only a finite number of queries and then rejects the input, $T'$ does not produce a $\dag$ on its output. So $T$ will differ from $T'$ in such a case. $T$ will simulate $M$ just as $T'$ does, but should the simulation come to the point, where $M$ would reject, $T$ will enter a loop in which it continually rewrites the content of the output square. Of course, the parallel simulation of oracle queries does not stop. This implies, that $w\in L(M)\Rightarrow T(w)=1$ as in proof 1 and $w\notin L(M)\Rightarrow T(w)=\dag \Rightarrow w\in L(A)$. \end{proof} We see, that the $\dag$ symbol is `stronger' then any non--$\dag$ symbol. What power does the use of this symbol provide us with? \begin{lma} $\forall L \in \iTTM{1}{\C{R}}:((\exists A=(T,Acc(A))):(L(A)=L \land \dag \in Acc(A))\Rightarrow L \in \Pi_2)$ \end{lma} \begin{proof} Let $A=(T,Acc(A)) \in \iTTM{1}{\C{R}}$ such that $\dag \in Acc(A).$ We will construct an oracle machine $M$ with a $\Sigma_1$ oracle such that $L(M)=L(A)^C$. $M$ will simulate the computation of $T$ and try to determine the output of $T$. We will ask the oracle, whether given a configuration of the transducer $T$, the content of the output changes after finite number of computational steps. If it does not, $M$ will know the output $\bar o_0$ of $T$ and will accept if $\bar o_0\notin Acc(A)$ and vice versa. Since $Acc(A)\in \C{R}$, this won't be a problem. If the content is to be rewritten, then $M$ can simulate the computation of $T$ to that point and then ask again. If $T(w)=\dag$ then $M$ never halts and thus does not accept $w$. Thus $w\in L(M) \iff T(w)\notin Acc(A)$. \end{proof} \begin{thm} \label{thm:iT-Pi2} $\{L\in \iTTM{1}{\C{R}}|\dag \in Acc(A)\} = \Pi_2$ \end{thm} \begin{proof} It is an obvious corollary of lemma 3 and lemma 4. \end{proof} \begin{cor} \label{cor:iT1} $\iTTM{1}{\C{R}}=\Pi_2\cup\Sigma_2$ \end{cor} \begin{proof} Follows on from Theorem \ref{thm:IT-S2} and theorem \ref{thm:iT-Pi2}. \end{proof} After these results, we might get the feeling, that in one square, we can compute the answer to one oracle call to a $\Sigma_2$ oracle. So if there was a larger output tape, we might be able to compute more. Since we know (see \cite{bieg-phd}), that for an oracle machine $k+1$ queries to $\Sigma_2$ are better then $k$ queries, it would be tempting to proof such a conjecture for our model. This will be the aim of the next section. We will formulate one more (obvious) property of the Coupled transducer machines. It is the fact, that if we have two machines, we can create a third one by `gluing' these two machines together. On the other hand, if we have one infinite time transducer machine using an output tape of size $k$, we can 'separate' it into two machines with output tapes of sizes $a$ and $k-a$ that will compute their respective parts of the output of the original machine. \begin{lma}[Concatenation lemma] Let $(T_1,S_1)$ and $(T_2,S_2)$ be two $CTM$, then there exist a machine $(T,S)$ such that $L(T,S)=L(T_1,S_1)\|L(T_2,S_2)$. If $(T_1,S_1)\in\iTTM{f(n)}{\C{L}_1}$ and $(T_2,S_2)\in\iTTM{g(n)}{\C{L}_2}$ then $(T,S)\in\iTTM{f(n)+g(n)}{\C{L}_1\|\C{L}_2}$. (The symbol $\|$ stands for concatenation). \end{lma} \begin{proof} $T$ will simulate parallel computation of $T_1$ and $T_2$ and write the output of $T_2$ right behind the output of $T_1$. There are many ways how to do this, we shall omit unnecessary technical details. $S=S_1\|S_2$. It is obvious, that $(T,S)$ satisfies our demands. The second part of the conjecture is also straight forward. \end{proof} We might refer to $T$ by writing $T_1\|T_2$. \end{section} %\begin{lma} %$\iTTM{k}{\C{R}}\subseteq \{L \in \Sigma_3| \exists$ oracle machine $M$ with an $\Sigma_2$ oracle such that $L(M)=L$ and $M$ needs mostly $k+1$ oracle calls\} %\end{lma} %\begin{proof} %Let $A=(T,Acc(A)) \in \iTTM{k}{\C{R}}$. %We will show how the corresponding oracle machine $M$ works. %First of all $M$ needs to compute the output of $T(w)$, given $w$ as an input. %To achieve this goal, $M$ will first find out positions of all $\dag$ in $T(w)$. %The $l$-th letter of the word $T(w)$ is not $\dag$ if and only if the following statement is true: % %$\exists m \in \N : \forall n \in \N : (n>m \Rightarrow Out_l(n)=Out_l(m))$. %In other words $\exists m \in \N : \forall n \in \N : (n>m \Rightarrow ( (q_0,BwB,1,\$B,0)\vdash_T^m (q,w',i,\$a_0\dots a_l\dots a_kB,i') %\Rightarrow (q_0,BwB,1,\$B,0)\vdash_T^n (q',w'',j,\$a_0'\dots a_l\dots a_k'B,j')))$ % %Since the body of the predicate is a recursive predicate, the set of all $w$ satisfying our statement is in $\Sigma_2$. %Thus $M$ needs only one query to find out whether the $l$-th bit of $T(w)$ is $\dag$. %Since $|T(w)|\leq k$ $M$ needs mostly $k$ queries so far. %Now, $M$ needs to find out what the remaining non-$\dag$ bits in $T(w)$ are and whether $T(w)\in Acc(A)$. %We will solve those two remaining tasks with one oracle call. %Let $a$ be the number of non-$\dag$ bits of $T(w)$, let $a$ be the number of such bits and let $i_l$ be the position of $l$-th %such bit in $T(w)$. %Let $P(v_1,v_2,\dots , v_a)$ denote such a word $w'$ that the $i_l$-th bit of $w'$ is $v_i$ and all of the remaining bits are $\dag$. %What we want to know is whether the following statement is true: % %$\exists m \in \N : \forall n \in \N : ( n>m \Rightarrow (o_{i_1}(n)=o_{i_1}(m) \land o_{i_2}(n)=o_{i_2}(m) \land \dots %\land o_{i_a}(n)=o_{i_a}(m) \land P(o_{i_1}(m),o_{i_2}(m),\dots,o_{i_a}(m)) \in Acc(A)))$. % %After a closer look, one can see that the body is again a recursive predicate and thus the whole statement represents a $\Sigma_2$ set. %If oracle response is affirmative $M$ accepts, if it is negative $M$ rejects. %It is obvious, that for $M$ as described above $L(M)=L(A)$ %\end{proof} \begin{section}{The Tape--size hierarchy} In this section, we will examine the relation between oracle machines with a $\Sigma_2$ oracle and Coupled transducer machines. The general result of this section is the proof, that output tape of fixed size $k+1$ is stronger, then the one of size $k$ for all $k$. We shall call the hierarchy established this way the \emph{Tape--size Hierarchy}. Since all the machines studied in this section have a constant bound of their output tape, their accepting sets can be reduced to finite sets. Thus in all the lemmas and theorems are the accepting sets of all machines bounded to be regular. By the fact mentioned above, this bounds cause no loss of generality. We shall begin with creating some tools, which we will use in the proofs that are to follow. \begin{lma} \label{lma:LE-S2} Let $T$ be a $ITTT$ with output tape fixed to the size $k$. Let $LE_T^\dag(w,n)$ denote a predicate which is true if and only if $\#_T^\dag(w)\leq n$. $\forall n\in \N : S_n^T\{w|LE_T^\dag(w,n)\}\in \Sigma_2$. \end{lma} \begin{proof} Let $T$ and $n$ be given. If we knew a lower bound for the number of non--$\dag$ symbols in $T(w)$, we would also know an upper bound for $\#_T^\dag(w)$ ($k$ minus the lower bound). Thus the set of all words whose output contains $k-n$ or more non--$\dag$ symbols is the same set as $S_n^T$. Formally $$\{w|k-\#_T^\dag(w)\geq k-n\}=\{w|\#_T^\dag(w)\leq n \}$$ Let $T_i$ be a $ITTT$ that writes only one symbol onto its output, namely the $i$-th symbol of the output of $T$. It can be easily seen that there is such a machine. Let $S$ be the set of all output symbols of $T$ except for $\dag$. Then $A_i=(T_i,S)$ is a $CTM$ accepting those $w$ for which the $i$-th letter of $T(w)$ is a non--$\dag$ symbol. Since $S_n^T$ is the set of all words whose output contain at least $k-n$ nice symbols, the following equation holds: $$S_n^T=\bigcup_{M\subseteq\{1,\dots,k\}\atop |M|=k-n}\bigcap_{i\in M} L(A_i)$$ From the theorem \ref{thm:IT-S2} we know, that $L(A_i)\in \Sigma_2$ for all $i$. Since $\Sigma_2$ is closed under union and intersection, $S_n^T$ is in $\Sigma_2$. \end{proof} Now, we can show how to simulate a fixed tape sized bounded coupled transducer machine by an oracle machine using only logarithmically many queries. \begin{lma} \label{lma:k-lgk} $\iTTM{k}{\C{R}}\subseteq \{L \in \Sigma_3| \exists$ oracle machine $M$ with an $\Sigma_2$ oracle such that $L(M)=L$ and $M$ needs at most $\lceil{\lg{(k+1)}\rceil}+1$ oracle calls\} \end{lma} \begin{proof} Let $L\in\iTTM{k}{\C{R}}$ and let $A=(T,Acc(A))$ be the appropriate machine accepting it. We will construct an oracle machine $M$ with the desired properties. Given $w$ on input, $M$ shall work the following way. As first, $M$ will compute $\#^\dag(w)$ the exact number of $\dag$ written on the output $T(w)$. We will show, that $M$ won't need more then $\lceil{\lg{(k+1)}\rceil}$ oracle queries to achieve this. Then $M$ will use only one more query to compute the output of $A$. Since $LE_T^\dag(w,n)$ can be computed using only one query (due to lemma \ref{lma:LE-S2}). $M$ can determine the value of $\#^\dag(w)$ by performing a binary search on the set $\{0,1,\dots,k\}$. This will obviously take no more than $\lceil{\lg{(k+1)}\rceil}$ oracle queries. Now, $M$ should find out what is the output of $T$ and whether it is in $Acc(A)$. We shall show that this can by achieved by using only one query. $M$ will ask the query, whether there exist such a number $t$, that after $t$ steps of $T$, all the convergent output squares have come to the point that they won't be altered in the forthcoming computation. And also if the word obtained by replacing the nonconvergent squares with $\dag$ symbols is in $Acc(A)$. We can write this in a formal way. Let $p_i; i\in \N$ denote the $i$-th prime ($p_0=2$). Let $P(v_1,v_2,\cdots,v_m,i_1,i_2,\cdots,i_m)$ denote a word of length $k$ such, that its $i_l$-th symbol is $v_l$ and all other symbols (whose indexes are not in the list) are $\dag$. Our question is\\ $(\exists t'\in \N )(\forall m\in \N):\Bigl(\left(t'=p_0^t\cdot\prod_{i=1}^{k-\#^\dag(w)+1}p_i^{\alpha_i}\right) \land \left( \bigwedge_{i=1}^{k-\#^\dag(w)+1}\alpha_i\neq 0 \right) \land$ $\left( \bigwedge_{i=1}^{k-\#^\dag(w)+1} o_{\alpha_i}(t)=o_{\alpha_i}(t+m)\right) \land$ $P\left(o_{\alpha_1}(t),o_{\alpha_2}(t),\cdots,\alpha_1,\alpha_2,\cdots, \alpha_{k-\#^\dag(w)+1}\right)\in Acc(A)\Bigr)$\\ Since the body of this predicate is recursive, the whole predicate refers to a set in $\Sigma_2$ and thus, we need only one query to obtain the answer to our final question. \end{proof} In the previous proof, we used the coding of lists of numbers into exponents of primes. Of course, we could have used any other numbering function. We will now show how to simulate an oracle machine that uses at most $k$ oracle calls by using an exponentially long tape. This result is somehow expectable from the knowledge of our previous lemma. \begin{lma} \label{lma:2^k} Let $M$ be an oracle machine that is allowed to make mostly $k$ oracle calls (to a $\Sigma_2$ oracle). Then $L(M)\in \iTTM{2^{k+1}-1}{\C{R}} $ \end{lma} \begin{proof} The proof has the following idea. Let $M$ be our oracle machine, let $O$ be its oracle and $w$ its input. If we remove or change $O$, we might get different computations. These computations will form a binary tree and in each branching, there will be an oracle query. We shall call this tree a decision tree. Since the number of queries to $O$ is bounded by $k$, the tree has mostly $2^k-1$ vertices. All that we need to do to ensure that we can correctly simulate $M$ with $O$ is to compute the answer to each query in the branching tree of $M$ on $w$. As we shall see, this can be achieved by an $ITTT$ with a sufficiently long output tape. We shall also compute the result of $M$ for each possible path of the computation. Since there are $2^{k-1}$ leafs (and each leaf is a query), there are $2^k$ possible computational paths (after the last query, there can still be some computation). To write all this information, we need a $2^k+2^k-1=2^{k+1}-1$ squares long tape. Having this information, we can easily find the real computation of $M$ on $w$ with $O$ as its oracle. We can effectively number each node in the decision tree. Let $T_i$ compute the output of the query with number $i$ and print $1$ if the answer is positive and $\dag$ if it is negative. The existence of such a $T_i$ is guaranteed by corollary \ref{cor:iT1}. Since each of the $2^k$ possible computational paths has a fixed unique combination of $k$ query answers, there is no problem to simulate the result of each such computation by a common Turing machine. Let $T'_i$ be a Turing transducer simulating $i$-th computational path and print the symbol $1$ if the computation accepts. By the use of the concatenation lemma, we can create an $ITTT$ such that the content of the $i$-th output square is the output of $T_i$ if $i<2^k$ or the output of $T'_{i-2^k+1}$ otherwise. Let $S$ be the set of words of length $2^{k+1}-1$ that are codes of computational trees as described above, for which the correct computational path accepts. Since this set is finite, it is surely in $\C{R}$. Thus $(T,S)$ is an appropriate $CTM$ simulating $M$. \end{proof} The results presented so far give us an idea of how strong the Coupled transducer machines with fixed size of the output tape are. By using lemma \ref{lma:2^k} we can see that with an output tape of size $2^{k+1}-1$ we could compute more, then we could with a $2^k-1$ squares long tape. But is it true that if we increased the maximum size of the output tape just by one square, we would obtain greater computational power? We shall show, that there is an affirmative answer to this question. In fact, our computational model with fixed size output tape is very similar to the model of a Turing machine making parallel queries presented by Richard Biegel in \cite{bieg-phd} \cite{bieg-sup}. So we will try to use similar proof techniques to achieve our goal. We will start by examining the properties of the predicate $PAR_T(w)$ which is true if the number of non--$\dag$ symbols is even. \begin{lma} If $(T,S)\in \iTTM{k}{\C{R}}$ then $L=\{w|PAR(T,w)\}\in\iTTM{k}{\C{R}}$. \end{lma} \begin{proof} Let $A=(T,S')$ where $S'=\{v|\# $non--$\deg$ symbols in $v$ is even$\}$. Obviously $L(A)=L$. \end{proof} \begin{lma} \label{lma:if-then} If $(\forall m \in \N)(\exists n\in \N)(\exists T\in \C{T}_n):(PAR_T\not\in\iTTM{m}{\C{R}})$ then $(\forall a\in \N) : \iTTM{a}{\C{R}} \subsetneq \iTTM{a+1}{\C{R}}$. \end{lma} \begin{proof} Let $$n'=\max\{n|(\forall T\in \C{T}_n) (PAR_T\in\iTTM{m}{\C{R}} \}.$$ Thus there exists a $T'\in \C{T}_{n'+1}$ such, that $$PAR_{T'}\not\in\iTTM{m}{\C{R}}.$$ Using the concatenation lemma we know, that there are machines $T_n$ and $T_1$ such that $T'=T_n\|T_1$ where $T_n$ has its output tape of size $n$ and $T$ has its output tape of size $1$. Since $$PAR_{T_n}\in\iTTM{m}{\C{R}} \land PAR_{T_1}\in\iTTM{1}{\C{R}}$$ we can find a machine in $\iTTM{m+1}{\C{R}}$ accepting $PAR_{T'}$. If $(T_0,S)$ is the machine accepting $PAR_{T_n}$ then we will construct the machine $A$ for accepting $PAR_{n'}$ as follows: $$A=(T_0\|T1,S') ; S'=\left\{w'| \left(w'=wv\right) \land \left((w\in S \land v=\dag) \lor (w\not\in S\land v\in \Gamma_{T_1})\right)\right\}.$$ Thus, $PAR_{T'}\not\in\iTTM{m}{\C{R}}$ and $PAR_{T'}\in\iTTM{m+1}{\C{R}}$. If there exists a $T'$ for each $m$, then $\iTTM{a}{\C{R}} \subsetneq \iTTM{a+1}{\C{R}}$ for all $a$. \end{proof} We will now show, that the assumption of the previous lemma holds true. \begin{lma} \label{lma:comb} Let $n\in\N$ and let $bin_i(n)$ denote the $i$-th bit in binary coding of $n$ ($bin_1(2)=1$ and $bin_0(2)=0$, $bin_0(n)$ is the parity of $n$). Then $bin_i(n)=bin_0 {n\choose{2^i}}$. \end{lma} %\begin{proof} We shall not provide proof of this lemma, since it is a well known combinatorial property. %However, the idea of the proof could be as follows. The result from the properties of the Pascal triangle. If we mark all the even color in it with white and all odd numbers with black, we can see that the "picture" formed this way reminds us of the Sierpinsky triangle. %\end{proof} \begin{lma} \label{lma:lg} If $(\forall T\in \C{T}) (PAR_T\in\iTTM{m}{\C{R}})$ then $(\forall T\in \C{T}_k) (\exists (T',f)\in \ITTM{m\cdot\lceil\lg{k}\rceil}{\C{TM}}$ computing $\#_T^\dag)$. \end{lma} \begin{proof} $T'$ will use $PAR_T$ to compute $\#_T^\dag(w)$ bit by bit. Obviously if $PAR_T(w)$ is true, then the last bit of $\#_T^\dag(w)$ $1$. (Since the parity of $\dag$ symbols is $1-PAR_T(w)$). Let $n$ denote the number of non-$\dag$ symbols in $T(w)$. Obviously $$n=k-\#_T^\dag\left(w\right).$$ Let $T_i$ denote the transducer computing the content of the $i$-th output square of $T$. Let $S$ be a subset of $\{1,2,\cdots,k\}$. Let $T_S$ be a transducer returning $1$ if $(\forall i \in S)(T_i(w)\neq\dag$ and returning $\dag$ otherwise. (Such a transducer obviously exists). We shall proof, that if $\C{S}_{2^j}$ is the set of all $2^j$ element subsets of $\{1,\cdots,k\}$ and $\bb{T}_{2^j}$ is the machine $$\bb{T}_{2^j}=\bigoplus_{S\in\C{S}_{2^j}}T_S$$ (where $\bigoplus$ denotes the concatenation operator) then $$PAR_{\bb{T}_{2^j}}(w)=bin_j\left(\right).$$ Let $S\in\C{S}_{2^j}$. If there is an $i$ in $S$ such that $T_i(w)$ returns the symbol $\dag$ then $T_S(w)$ returns $\dag$ also. On the other hand, if there is no such $i$ in $S$, then $T_S(w)$ returns the symbol $1$. Let $n$ denote the number of non-$\dag$ symbols in $T(w)$. For many sets in $\C{S}$ is $T_S(w)\neq\dag$? Since the size of each $S$ is $2^j$, there are $n\choose{2^j}$ such sets. By lemma \ref{lma:comb} we can see, that $$PAR_{\bb{T}_{2^j}}(w)=bin_0{n\choose{2^j}}=bin_j(n).$$ This way, $(T',f)$ can compute $n$ in the following way. Let $PAR_{\bb{T}_l}=(T_{PAR_{\bb{T}_l}},A)$. Let us presume, that $T_{PAR_{\bb{T}_l}}$ always produces an output of size $m$ (we can achieve this by adding necessary padding and appropriately change the set $A$). Let $J_k$ be the set of all powers of $2$ smaller or equal to $k$. Then $$T'=\bigoplus_{l\in J_k}\left( T_{PAR_{\bb{T}_l}}\right).$$ Since each $PAR$ needs only $m$ squares, $T'$ needs $m\cdot\lceil\lg{k}\rceil$ squares. All that needs to be done now is the calculation of $n$ and then $\#_T^\dag(w)$. This is the task for $f$. Since $A$ is a finite set and the size of output of each $PAR$ is normalized to $m$, $f$ can comfortably transform each block of length $m$ to a $0$ or $1$ depending on its correspondence to $A$. Since $k$ is fixed, $f$ can have the knowledge of it. Thus it can be computed as $$\#_T^\dag(w)=k-n.$$ Since $T$ and $k$ are fixed, there can always exist an $(T',f)$ as described above. \end{proof} \begin{lma} \label{lma:if} $(\forall m \in \N)(\exists n\in \N)(\exists T\in \C{T}_n):(PAR_T\not\in\iTTM{m}{\C{R}})$ \end{lma} \begin{proof} By contradiction.\\ Let $(\exists m \in \N)(\forall n\in \N)(\forall T\in \C{T}_n):(PAR_T\in\iTTM{m}{\C{R}})$ be true. Then by lemma \ref{lma:lg} for each $T\in\C{T}_k$ there is a $M=(T',f)\in\ITTM{m\cdot\lceil\lg{k}\rceil}{\C{TM}}$ computing $\#_T^\dag$. We will construct an oracle machine $M'$ simulating $A=(T,Acc(A)$ with only $\lceil\lg(m\cdot\lceil\lg{k}\rceil+1)\rceil+1$ oracle queries. $M'$ is a strong similarity between the computation of $M'$ and the machine used in lemma \ref{lma:k-lgk}. The main difference will be, that $M'$ will use $T'$ to compute $\#_T^\dag$. $M'$ will at first compute the output of $T'$. To do this $M'$ will first enumerate the number of $\dag$ symbols in the output of $T'(w)$. Since $$|T'(w)|=m\cdot\lceil\lg{k}\rceil$$ this can be done by $$\lceil\lg(m\cdot\lceil\lg{k}\rceil+1)\rceil$$ queries. Now $M'$ will compute the output of $T'$, calculate $\#_T^\dag$ and then simulate the output of $T$. This computation can be realized by on oracle machine $M''$ using a $\Sigma_1$ oracle. The result of $M''$ can be obtained by one query of $M'$. The computation of $M''$ is equivalent to this predicate (we use similar notation as in lemma \ref{lma:k-lgk}), where $m\cdot\lceil\lg{k}\rceil-\#_{T'}^\dag(w)+1$ is denoted $\#$ and $f\left(P\left(o^{T'}_{\alpha_1}(t),o^{T'}_{\alpha_2}(t),\cdots,\alpha_1,\alpha_2,\cdots, \alpha_{\#}\right)\right)$ is denoted $f^{T'}_{1:\#}$ :\\ \vskip5pt$(\exists n\in\N)(\forall l\in\N):(\left( n=p_0^t\cdot \prod_{i=1}^{\#+f^{T'}_{1:\#}} p_i^{\alpha_i}\right) \land$ $\left( \bigwedge_{i=1}^{\#+f^{T'}_{1:\#}}\alpha_i\neq 0 \right) \land$\\ $\left( \bigwedge_{i=1}^{\#} o^{T'}_{\alpha_i}(t)=o^{T'}_{\alpha_i}(t+l)\right) \land$ $\left( \bigwedge_{i=\#+1}^{\#+k-f^{T'}_{1:\#}} o^{T}_{\alpha_i}(t)=o^{T}_{\alpha_i}(t+l)\right) \land$ \\ $P\left(o^{T}_{\alpha_{\#+1}}(t),o^{T}_{\alpha_{\#+2}}(t),\cdots,\alpha_{\#+1},\alpha_{\#+2}, \cdots, \alpha_{\#+k-f^{T'}_{1:\#}}\right)\in Acc(A)\Bigr).$\\ \vskip5pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% TU DADKA SKONCILA KONTROLU Let $M_0$ be a Turing machine with a $\Sigma_2$ oracle such that $M_0$ needs $2^i$ oracle calls to accept $L(M_0)$ and that there is no $\Sigma_2$ oracle machine $M_1$ accepting $L(M_0)$ with less then $2^i$ oracle calls. Due to results in \cite{bieg-sup} there is such an $M_0$ for each $i$. Then by lemma \ref{lma:2^k} $$L(M_0)\in \iTTM{2^{2^l+1}-1}{\C{R}}.$$ But if this is true, then by the previous construction $L(M_0)$ can be computed by making only $$\lceil\lg(m\cdot\lceil\lg{2^{2^i+1}-1}\rceil+1)\rceil\leq \lceil\lg(m\cdot2^i+1+1)\rceil\leq \lceil\lg{m}+1+i))\rceil\leq m+i+1$$ queries. Since $\lg m$ is constant, there exists an $i$ big enough to make the following inequality hold $$m+i+1<2^i.$$ But this is a contradiction, since there cannot exist a machine $M_1$ accepting $L(M_0)$ by making only $m+i+1$ queries. \end{proof} \begin{thm} $k$ %exists its prefix code $$ for which for all $w$ in $\abc^\ast$ %$$ w\in L(M) \iff w \in L(U).$$ %Then the language $L_{\bar \C{C}}=\{| \not\in L(M)\}$ and let there exist a code for each machine from this class. Then no machine in $\C{C}$ can accept the language consisting of codes of machines rejecting their own codes. We shall denote this language by $D_{{\C{C}}}$ and call it the diagonal language for $\C{C}$. \end{lma} \begin{proof} By contradiction.\\ Let $A$ be such a machine. Does $A$ accept its own code? If this was the case, then the code of $A$ could not be in $L(A)$ since this is the language of all codes that are rejected by machines they represent. Thus $A$ cannot accept it own code. But if $A$ does not accept its own code, then the code of $A$ must be in $L(A)$, since this is the language of all codes that are rejected by machines they represent. Thus $A$ must accept its own code. Since this is a contradiction, there cannot be such an $A$. \end{proof} We shall now start to examine the relations between concrete acceptor classes by showing, that regular acceptors are weaker then context--free acceptors. This result will be achieved by providing a machine using a context--free acceptor accepting $D_{{\iTTM{<\omega}{\C{R}}}}$. \begin{lma} \label{lma:R_CF} $D_{{\iTTM{<\omega}{\C{R}}}} \in \iTTM{<\omega}{\C{L}_{CF}}$ \end{lma} \begin{proof} Let $A$ be a finite automaton with its code $$ and let $T$ be an $ITTT$ with code $$. Thus $M=(T,L(A))\in \iTTM{<\omega}{\C{R}}$ and $$ is a proper code of $M$. The machine $M_D=(T_D,L(A_D))$ (where $A_D$ is a push--down automaton) accepting the diagonal language shall work in the following way. Given $$ on input, $T_D$ will output the output of $T$ concatenated with all words of size $T()$ (we shall denote this number by $P$) and for each such word there will be the information, if $A$ accepts it. For better under standing look at the following figure:\\ \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline $T()$&$w_1^R$&$A(w_1)$&$w_2^R$&$A(w_2)$&$\cdots$&$w_P^R$&$A(w_P)$\\ \hline \end{tabular} \end{center} \vskip0.6cm Then $A_D$ will read the output $T()$ into its buffer and continue to move along the output tape. If $A_D$ should read $()^R$ ($A_D$ can find this out with the use of non-determinism) then it will compare letter by letter it with the content of its buffer. After verifying, that the read block was really $()^R$ $A_D$ reads the next letter. It is the symbol $1$ if $\in L(A)$ and $0$ otherwise. If it was the symbol $0$, $A_D$ enters an accepting state, reads the remaining part of the output tape and accepts. If the symbol red by $A_D$ was $1$, then the automaton enters a non accepting state, reads the remaining content of the output tape and rejects. Thus we created a machine $T_D\in\iTTM{<\omega}{\C{L}_{CF}}$ accepting $D$. Some technical notes: The codes of $A$ and $T$ can be understood as codes of respective Turing machine or transducer. The computation of $T_D$ works the following way. If $T$ should come to the point, that it needs more output tape (i.e. it would be rewriting a $B$ symbol on its output tape), $T_D$ can rewrite the contents of its output tape following after the output of $T$ by all possible words of the required length. Since the output of $T$ is always finite, there are no problems with this and no unwanted $\dag$ symbols won't be created. Once all the words of the appropriate size are written, $T$ may simulate $A$ on their reverses and print the output of each such simulation after the respective word. After all this has been done, $T_D$ may continue in the simulation of $T$. Since the output of $T$ is finite the output of $T_D$ will be also finite, thus $T_D\in \C{T}_{<\omega}$.\\ Some more technical notes: Since $T_D$ cannot create a $\dag$ symbol in finite time, it would seem impossible to both generate all possible outputs of $T$ and then simulate $A$ on them. Although this can be done by using two squares of $T_D$'s output tape to encode one square of the output tape of $T$. For example, we might code a square containing letter $X$ by a pair of squares $XX$. This way, we can also code the $\dag$ symbol by a pair of letters not used so far. Naturally, $T_D$ shall simulate $A$ reading two letters as one. To avoid ambiguity, $T_D$ shall use delimiters on its output tape to separate the output of $T$, all its possible outputs and results of each machine. We can use another so far unused pair of letters to represent the delimiter. This also means, that $A_D$ must work with pairs of letters and interpret them correctly, but this is obviously no problem. Thus $M_D=(T_D,L(A_D))$ is a machine in $\iTTM{<\omega}{\C{L}_{CF}}$ accepting $D$. \end{proof} Now, we can proof our firs result. \begin{thm} \label{thm:R$ where $$ is the code of the transducer $T$ and $$ is the code for the push-down automaton accepting $L(A)$. Then the machine $M_D=(T_D,L(A_D)) \in \iTTM{<\omega}{\C{L}_{ECS}}$ for accepting the diagonal language operates the same way as in the previous proof, only the reverses are not necessary any more and $T_D$ simulates the computation of a push--down automaton. \end{proof} \begin{thm} \label{thm:CF$ where $$ is the code of the transducer $T$ and $$ is the code for always halting Turing machine accepting $L(A)$. Then the machine $M_D=(T_D,L(A_D)) \in \iTTM{<\omega}{\C{L}_{REC}}$ works the following way. The output of $T_D$ shall be $$ followed by a delimiter and the output of $T$. Since there exists a universal Turing machine $U$, $A_D$ shall simulate this machine on $$. Since $$ always halts, the computation of $U$ halts with the same result. $A_D$ halts with accepting if $A$ rejected and vice versa. \end{proof} \begin{thm} \label{thm:ECS$ where $$ is the code of the transducer $T$ and $$ is the code for always halting Turing machine accepting $L(A)$. Then the machine $M_D=(T_D,L(A_D)) \in \iTTM{<\omega}{\C{L}_{RE}}$ works the following way. The output of $T_D$ shall be $$ followed by a delimiter and the output of $T$. Since there exists a universal Turing machine $U$, $A_D$ shall simulate this machine on $$. Since $$ always halts, the computation of $U$ halts with the same result. $A_D$ halts with accepting if $A$ rejected and vice versa. \end{proof} \begin{thm} \label{thm:REC