2

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.

Pteromys
  • 7,220
  • What does "prefix-free" mean in this context? Does "a TM whose domain is prefix-free" mean that if $U$ terminates on $\rho x$ then it has to diverge on $\rho xw$ if $w$ is nonempty, no matter what $\rho$ is? – hmakholm left over Monica Dec 17 '13 at 13:56
  • 1
    @HenningMakholm The answer to your second question is "Yes." – Pteromys Dec 17 '13 at 14:46
  • 2
    @Henning: this is a standard concept in Kolmogorov complexity. A language is prefix free if it contains no pair of strings one of which is a proper prefix of the other; a machine is prefix free if the language it accepts is prefix free. – Carl Mummert Dec 18 '13 at 22:07

2 Answers2

5

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.

hmakholm left over Monica
  • 286,031
  • Given $px$, how do you figure out what $p$ is? – Christopher King Dec 13 '18 at 20:15
  • @PyRulez: I'm assuming we're using a scheme for encoding Turing machines as symbol strings which is self-delimiting such that this is a trivial task. It is easy to see that such schemes exist (if everything else fails, take your favorite scheme and prepend a length in unary to every machine description -- as you do in your answer!). And the way the problem is set we only need to construct $U$ for one particular encoding of our own choice. – hmakholm left over Monica Dec 13 '18 at 23:54
0

Here is another way.

Let $p_f$ be a computable prefix code for partial recursive functions. For example, you could let $p_f$ be $0^{|d(f)|}1d(f)$, where $d(f)$ is a description of a turing machine computing $f$. Then given $p_fx$, we can compute $p_f$ and $x$.

Now, let $y$ be the empty string. Now perform the following algorithm:

  1. Enumerate the domain of $f$.
    • If $y$ is enumerated, check if $x$ is empty. If it is, output $f(y)$. Otherwise, reject (or diverge).
    • If $s$ is enumerated, where $y$ is a prefix of $s$, remove a symbol from the beginning of $x$ and add it to the end of $y$, and go back to step 1.

If $f$'s domain is prefix free, then $U(p_fx)$ will compute $f(x)$ if $x$ is in $f$'s domain, and otherwise diverge (which is fine). If $f$'s domain is not prefix free, $U(p_fx)$ will do something else. Either way, $U$ will have a prefix free domain.

Christopher King
  • 10,365
  • What happens in the second bullet if $x$ is already empty? If you reject in that case I think you reach the same restriction of $f$ as I do in my construction, assuming the enumeration is in order of increasing computation length. – hmakholm left over Monica Dec 14 '18 at 00:11