
Let $\Sigma$ by a finite set of letters. The set
$\Sigma^n$, where $n$ is a natural number,
is the set of all strings of length $n$,
and $\Sigma^*$ is the union of $\Sigma^n$ for all
$n$.  A subset of $\Sigma^*$ is said to be a {\em language}.
We are concerned with the complexity of determining
membership in a language, that is, the number of
computational steps required to determine if any
given $l\in \Simga^*$ is in $L$.

The formalism of computation is a {\em Turing Machine.}
The $l\in \Sigma^*$ is written onto its tape and the
Turing Machine's program is started.
There exist three possibilities for the out come of
the computation:
\begin{enumerate}
\item The program {\em accepts} the string $l$. This
  is taken to mean that $l\in L$ and
  is signified by the Turing Machine Halting in a certain
  state or set of states called {\em accepting states.}
\item The program {\em rejects} the string $l$. This
  is taken to mean that $l\not\in L$ and is signified
  by the Turning Machine halting in a certain
  state or set of states called {\em rejecting states.}
\item The program {\em diverges}, that is, 
  the computation does not halt.
\end{enumerate}
We consider the possibility of a map from languages
to Turing Machines which assigns to language $L$ the
Turing Machine $T_L$. We denote the computation of
$T_L$ on an $l\in \Sigma^*$ by $T_L(l)$. The result
of the computation is either accept, reject or diverge.

Hence $T_L$ can be seen as a function. However, it is
also a particular machine, and $T_L(l)$ is not only
the result of the computation, but represents the 
computation itself. We are concerned with the length
of time of the computation. Denote this by
$\# T_L(l)$. Then from $T_L$ we derive a partial function
$\#T_l:\ZZ\rightarrow\ZZ$ defined by,
\[ (\#T_L)(n) = \max\{\, \# T_L(l), l\in\Sigma^n\,\}.\]
For most purposes, this notation is only applied to
Turing machines which are guarenteed not to diverge, hence
the function is total.

If for a language $L$ there exists a Turing Machine
$T_L$ such that $T_L(l)$ accepts if $l\in L$ and
$T_L(l)$ rejects if $l\not\in L$, and there exists
a polynomial function $f(n)$ such that
$(\#T_L)(n) \le f(n)$, then the language $L$ is said
to be {\em Polynomial Time Recognizable}, and is
denoted $L\in P$. That is, $P\subset 2^{\Sigma^*}$ is
the set of all languages such that there exists a
Turing Machine accepting the members of the language,
rejecting the non-members, and doing this within a time
bound polynomial in the length of the string.





