Counter Predictor

Despite its “universality” (see The Universal Counter) a counter can not be used as a universal machine for a sequence prediction simply because if you think to an empirical test for example to search for the first occurrence output “101” you will find …1010 and then …1011 and then again …10100 and son on . So the shortest answer is alway X0 whereXx is the bit string to search .  The question is : why  can I not use a counter as universal machine in a sequence prediction? Is the universality not enough for a sequence predictor ?  I found an almost satisfactory answer. A counter can not be used as a predictor because to measure how much good the prediction is we need to count how many bits of information we need to identify the result . With a counter to identify a N length bitstring we need about N bits so we have not compression and the prediction is absolutely wrong .

This is a simple observation but what this fact suggest is that the size of the output of a universal machine is not irrelevant but it has an important role for sequence prediction. In the case of a counter we have an output that grow with a complexity O(LogN) increasing the time but on the other side we have the same problem with a machine with an output with a complexity of O(2^N) in both cases we don’t gain bit of information to identify the prediction. Which is the best output size?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s