On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence

Details On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence

2009-11-23

arxiv.org/abs/0911.4521v1

Computer Science

Computational Complexity

25 pages

Scientific paper

It is shown that the length of the algorithmic minimal sufficient statistic of a binary string x, either in a representation of a finite set, computable semimeasure, or a computable function, has a length larger than the computational depth of x, and can solve the Halting problem for all programs with length shorter than the m-depth of x. It is also shown that there are strings for which the algorithmic minimal sufficient statistics can contain a substantial amount of information that is not Halting information. The weak sufficient statistic is introduced, and it is shown that a minimal weak sufficient statistic for x is equivalent to a minimal typical model of x, and to the Halting problem for all strings shorter than the BB-depth of x.

Affiliated with

Also associated with

No associations

Rating

On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-279308