Message Boards Message Boards

0 Replies
0 Total Likes
View groups...
Share this post:

Shortest meta-circular description of a universal computational structure

Posted 9 months ago

The question "What is the shortest description of a universal computational structure that includes a meta-circular evaluator?" gives rule 110 as an example of a short rule that is incapable of short homoionic (meta-circular) description. This is important as it provides closure on Kolmogorov Complexity's choice of UTM.

This is a different kind of question than asking, "What is the UTM with the shortest description?"

Restating the question in computerdom vernacular:

What is the shortest known program that simulates the Universal Computation machine on which it runs?

In other words, the program is an interpreter that if you feed it a binary to execute, will produce exactly the same result as if you had fed the binary to the machine directly.

This would seem to overcome a (rather pedantic IMHO) objection to Algorithmic Information approximation as the most principled information criterion for model selection: That the choice of instruction set is arbitrary. As such it would seem to be an appropriate prize challenge running in parallel to the Hutter Prize and for similar reasons.

PS: In the few online conversations on this question I've run across since 2002, there are various games one can play to try to evade this question such as arise when people talk about the combinatorial calculus (SK combinators) or other concatenation formal languages as requiring descriptions external to their physical implementation. To these objections I can respond with my original suggestion to Hutter which was that to whatever level of abstraction of the physical one may wish to take as "real", there is still the challenge of simulating that level of physical abstraction as the substratum of universal computation. So pick your level. NOR gates? Maxwell’s equations? QED? The point is that these are not arbitrary.

POSTED BY: James Bowery
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract