Let $\phi$ be a the function computed by a universal Turing machine: $\phi_y(x)$ is the encoding of the output of the machine for the program whose Gödel encoding is $y$ with input encoding $x$.

I am looking for an upper bound on the length of the shortest program that computes $\phi$.

  • $\begingroup$ I've edited in what you added in this comment thread. I don't think the question quite makes sense, but I've reopened the question because I think you misunderstood something and hopefully someone can explain. $\endgroup$ – Gilles 'SO- stop being evil' Dec 20 '13 at 10:41
  • $\begingroup$ John Tromp has constructed some small UTM's (in the context of combinatory logic): homepages.cwi.nl/~tromp/cl/cl.html. $\endgroup$ – Yuval Filmus Dec 22 '13 at 5:35

The precise answer depends on the model of computation and on the specifics of the encodings for $x$ and $y$ -- so if you want an answer, you'll need to specify those.

In general, once you specify those, the way we get an upper bound is by writing an interpreter that interprets the Turing machine $y$ on input $x$; then we look at the length of that interpreter. So, that should tell you how to get an upper bound for yourself.

In any case, the upper bound will always be some constant, i.e., $O(1)$ (for trivial reasons).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.