The letters $v,t,s,h,q$ denote the current tape string, time step, maximal space used (defined as the number of different tape cells), head position and machine state, respectively. Note that the recursively define function might never terminate, and so $\mathrm{run}_M$ is in general only a partial function of it's defined domain.

The standard mathematical definition of a Turing machine $M$ specifies a working memory alphabet $\Gamma$ and an input alphabet $\Sigma\subset\Gamma$ and also encodes machine states $Q$ and a transition function $\delta: Q\times\Gamma \to Q \times \Gamma \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}$. However, it does not formalize the concept of the working memory as such, which is usually imagined as an infinitely long tape containing characters from $\Gamma$.

This entry defines an interpreter for a Turing machine, i.e. a partial function $\mathrm{run}_M(v,t,s,h,q)=\langle v',t',1,1,q\rangle$, where the tape string $v'$ is the result of applying $\delta$ again and again until the output doesn't change, and $t'-t$ then documents the number application which were necessary. Also $q$ is the state, $h$ is the current head position and $s$ is the maximal space used during the computation.

Note that for Turing machines $M,M'$ with compatible alphabets we have $\mathrm{run}_{M'}\circ\mathrm{run}_{M}=\mathrm{run}_{M' \mathrm{concatenate}\, M}$. So for example $\mathrm{run}_{M}\circ\mathrm{run}_{M}=\mathrm{run}_{M}$.

We denote its output of $M\in\mathrm{TM}$ on $v$ by

and it's runtime by

For the output of a k-tape Turing machine (I didn't formalize the output of a k-tape Turing machine here, but I'd say it's straight forward in principle), which is instantiated by $k$ input strings, we adopt another function notation and separate the input by commas. E.g. for $M\in\mathrm{TM}_2$ and input data $v,w$, we write $M(v,w)$.

Denote an encoding of mathematical objects to strings by $\llcorner\ \lrcorner$. Let $f:X\to Y$ be a partial function so that all arguments arguments and values can be encoded.

Note that this is a definition of a predicate on the Turing machine $M$ (i.e. set tuples like they are defined in k-tape Turing machine) and not on its associated partial function mapping strings to strings. Remember that a partial function is a relations with arbitrarily declared domain and $f(a)=b\equiv \langle a,b\rangle\in f$, i.e. a partial function is just a set of argument-value pairs. The expression on the right hand side of the above definition is involves first passing from $M$ to $\mathrm{run}_M$, which is an object from which the transition function $\delta$ of $M$ cannot be uniquely reconstructed. So two Turing machines $M,M'$ can be different, e.g. they might have a different runtime, but compute the same function!

Let $L\subseteq\{0,1\}^*$ be a set of bit strings and let $\chi_L:\{0,1\}^*\to\{0,1\}$ be the associated characteristic function.

That the point a language $L$ just has to be an abstractly definable set. The characteristic function $\chi_L$ is then again defined using the set-membership predicate $\in$ and is therefore not necessarily computable. Indeed, if the Church Turing thesis holds, then it's in any practical sense computable exactly if there is a Turing machine $M$ for which $M\ \mathrm{decides}\ L$ holds.

(Hopefully not too confusing remark: The purpose of the last two predicates is to reason about the computability of certain sets (functions, languages), e.g. $M\ \mathrm{computes}\ f$ reasons about $f$. To go one meta level up we can reason about the computability predicate itself. Note that unfortunately we can only define computability by the partial function associated with a Turing machine. Then the Halting problem implies that we can't decide for which $x$ the expression $M(x)$ denotes a set and so the truth of falsehood of a statement like “$M\ \mathrm{computes}\ f$” might turn out to be itself uncomputable/unprovable.)

Now let $T:\mathbb N\to\mathbb N$ and denote the length of the string $v$ by by $\left|v\right|$. Note that $T(n)$ denotes the body of the function $\lambda n.T(n)$, i.e. $n$ is a placeholder for a function argument.

Switching from a $k$-tape machine to a 1-tape machine, which has the same input-output behavior, modifies the runtime at most as $\mathcal O\left(T(n)\right)\to \mathcal O\left(T(n)^2\right)$. The trick is to partition the tape into a grid of length $k$, e.g. the information from tape $2$ are positioned at $2,2+k,2+2k,2+3k,\dots$. A more precise bound for the time scaling is $5k\cdot T(n)^2$, the $5$ coming from additional necessary left-right-left-right-left-sweepings of the head over the whole tape.

Switching from one machine $M$ with alphabet $\Gamma$ to another $M'$ with the small alphabet $\{\triangleright,\Box,0,1\}$ modifies the runtime at most by a factor logarithmic in $\left|\Gamma\right|$

Wikipedia: Computational complexity of mathematical operations

Partial function, k-tape Turing machine