How can a non-deterministic Turing Machine be converted to a deterministic TM with a witness-input?

Question

This 2014 paper by Barak and Goldreich defines the notion of a universal set $S_{\mathcal{U}}$ as the set of all tuples $(M,x,t)$ such that the non-deterministic machine $M$ accepts the input $x$ in $t$ steps or less (page 2). They further go on to describe a relation $R_{\mathcal{U}}$ for $S_{\mathcal{U}}$ which they call the 'natural witness-relation,' defined as

$$R_\mathcal{U}\equiv\{((M,x,t),w)\mid M\text{ accepts $(x,w)$ in $t$ steps or less}\}$$

Here $M$ is changed from a non-deterministic machine to a two-input deterministic machine. Since the purpose of this relation seems to be to list all instance-witness pairs, if I am understanding it correctly then $w$ is a witness for instance $x$ of the problem decided by $M$. That an NDTM can be expressed as a DTM is trivial.

However, just exactly how is the arbitrary machine $M$ in $S_\mathcal{U}$ transformed into the one that accepts $(t,w)$ in the definition of $R_\mathcal{U}$? Is the relation well-defined for arbitrary machines?

Sorry if the question is trivial, I come from a cryptography background and this is my first time dealing with these notions.

Answer 1

Let $\delta:\Sigma\times Q\rightarrow \mathcal{P}(\Sigma\times Q\times\{L,R\})$ be transition function of nondeterministic Turing Machine $N$. So for a given input $(a,q)$ where $a\in \Sigma$ and $q\in Q$, the machine $N$ has possibly lots of choices to transit.

In order to transform a Nondeterministic TM $N$ for input $x$ to a deterministic TM $D$, we can give the path of correct choices (that is which choice of transition it should choose) of transition function as a witness or certificate that TM $N$ can accept $x$. The deterministic machine $D$, use $N$ and this path to check whether $N$ reach accept state for input $x$ in $t$ steps or not.