How can one construct a universal prefix-free Turing machine (TM)? By a universal prefix-free TM, I mean a prefix-free TM $U$ (that is, a TM whose domain is prefix-free) such that for every prefix-free partial recursive function $f$, there feasibly exists $\rho_f$ such that $U(\rho_fx) = f(x)$ for any $x$.
I read the construction by Downey and Hirschfeldt, but I need a detailed construction, partly because I am unfamiliar with the convention in this field. For example, how can one construct a universal prefix-free TM from a (usual) universal TM?
Thank you for you help in this matter.
Given input $\rho x$, start by simulating $T_\rho$ on input $x$ until it halts, counting steps. (If it doesn't halt, then just diverge).
Let $n$ be the number of steps it takes for $T_\rho$ to halt on $x$.
Now enumerate all strings $y$ that are either prefixes of $x$ or have $x$ as a prefix and are at most $n$ symbols long. (There are finitely many such $y$s of course). Simulate $T_\rho$ on each of them for up to $n$ steps. If $T_\rho$ halts on one of the $y$s in $\le n$ steps, then diverge!
If none of the $y$s halt within the time limit, then halt with the output of $T_\rho$ on $x$.
It's clear that this works just as a universal machine if $\rho$ is actually a description of a prefix-free machine. On the other hand, the process is prefix-free by construction: it cannot halt on both $\rho x$ and $\rho xw$ because if $T_\rho(x)$ and $T_\rho(xw)$ both halt, the one that does so last will diverge in the above procedure.